Assign4V0
COMP2150 Assignment 4 Winter 2017
1
Due:
April 21, 2017, before 11:59 pm.
Notes
• Please follow both the “Programming Standards” and “Assignment Guidelines” for
all work you submit. Programming standards 1-25 are in effect.
• Hand-in will be via the D2L Dropbox facility. Make sure you leave enough time
before the deadline to ensure your hand-in works properly.
• All assignments in this course carry an equal weight.
Question 1: Introduction to Ruby
In the first part of this question you will implement a Stack and a Queue (as linked
structures) in a Ruby module. You will then use the module to make a simple calculator.
Part A: A4DataStructures.rb
Implement the A4DataStructures module as described below.
The Node class is a standard singly-linked Node. The initialize() method must accept 0, 1 or
2 parameters (if 1 is provided, use it to initialize the data; if 2 are provided, initialize the
data and link). Provide a to_s() method which returns a string representation of the data
item. Have Ruby automatically generate any necessary getters/setters
(accessors/mutators).
The AbstractList class implements a ‘standard’ singly-linked list. It must be ‘abstract’ in the
sense that you should prevent it from being instantiated. It must support the following
methods: insertFront(item), insertBack(item), removeFront(), empty?() and to_s(). (The
to_s method may be useful in debugging your program.) The insertFront, insertBack and
removeFront methods must have protected visibility (how does this differ from Java’s
version of protected?).
The Stack class extends AbstractList to implement a basic stack with push(item), pop(),
and top() methods. The Queue class extends AbstractList to implement a basic queue with
enqueue(item) and dequeue() methods.
These last two classes are examples of limitation. How are you hiding the underlying
methods of AbstractList from being accessed?
Part B: A4Calculator.rb
This program will make use of the module you created in Part A to evaluate simple integer
expressions, e.g. (2 + 3) * 4.
The expressions are limited to the following:
• Single digit, unsigned integers, i.e. 0…9. Signed numbers are not allowed. However you could
‘create’ larger numbers or negative numbers using arithmetic (e.g. 4*5, 0-1).
COMP2150 Assignment 4 Winter 2017
2
• The five ‘basic’ operators, +, -, *, / and %.
• Parentheses, ‘(‘ and ‘)’.
• Blanks, which are ignored.
The expressions will be read from standard input, one per line (You can use
line=$stdin.readline). Processing will continue until a blank line is entered. You can
assume that all the expressions are valid, “infix” expressions (i.e. the operator is between
the left and right operands).
Evaluation is done in two steps:
1. Convert the infix expression into the equivalent postfix (also known as Reverse Polish
notation) expression. A postfix expression places the operator after the two operands (e.g. 2
3 +).
2. Evaluate the postfix expression. Postfix expressions contain no brackets and evaluation is
straightforward using an evaluation stack.
Conversion of infix expressions to postfix employs both a queue (to hold the resulting
postfix expression) and a stack (to temporarily hold operators). It is known as the
“Railroad” algorithm, because in diagrams the operator stack is shown as a “sidetrack” for
shunting operators before moving them to the output.
To use the railroad algorithm, we assign priority levels to the operators, and to the left
parenthesis, as follows:
• Multiplicative operators (*, /, %): 2
• Additive operators (+, -): 1
• Left parenthesis ‘(‘: 0
We use the priority levels to decide when to store an operator, and when to copy it to the
output postfix expression. Here is a pseudo-code description of the conversion method.
Writing a priority() method would be helpful.
convertToPostfix (infix){
Queue postfix = new Queue()
Stack opStack = new Stack()
for (each character c in infix)
if (c is a blank) discard
else if (c is a digit) postfix.add(c)
else if (c is ‘(‘) opStack.push(c)
else if (c is ‘)’)
while (opStack.top != ‘(‘) postfix.add(opStack.pop)
opStack.pop // discard the ‘(‘
else // c is an operator
while !opStack.isEmpty && prio(c) <= prio(opStack.top)
postfix.add(opStack.pop)
opStack.push(c)
// end of for loop
COMP2150 Assignment 4 Winter 2017
3
pop remaining operators in opStack and add to postfix
return postfix
}// convertToPostfix
In the resulting postfix expression, the parentheses from the infix expression have been
discarded, the digits are in the same order as in the infix expression, and the operators will
be ordered in the order that they will be carried out.
For example: infix: 2 * (3 + 4); postfix: 2 3 4 + *.
The evaluation method is somewhat simpler than the conversion method. It uses a stack to
store intermediate results in the evaluation. When the algorithm finishes, there is a single
value left on the stack, which is the result of the expression itself. Here is a pseudo-code
description of the evaluation method.
evaluate (postfix){
Stack evalStack = new Stack()
while (!postfix.isEmpty)
op = postfix.remove
if (op is in '0'..'9')
convert to corresponding int and push onto evalStack
else // it is an operator
right = evalStack.pop
left = evalStack.pop
if(op is division or remainder)
if(right is zero) error("division by zero")
else
result = left op right
evalStack.push(result)
// end of while loop
return evalStack.top
}// evaluate
When evaluating division operations (/ or %) you must check for division by zero. Note
that when popping operands off the stack, the right one is popped first (Why?). Use the eval
method to evaluate the result. When displaying the result of the evaluation, echo the
original input and the result (e.g. (2 + 3) * 4 = 20)
Submission
Submit two files (A4DataStructures.rb and A4Calculator.rb).
Submit all files on D2L.