CS 240: Lecture 13 – Stacks and Queues Continued
Dear students:
Today we continue our discussion of stacks and queues through some exercises.
Postfix Evaluation
Let’s see an example of an algorithm that uses a stack. Support you want to write code to evaluate an arbitrary arithmetic expression. Something of this form:
You might break the expression up into a list of tokens and then iterate through it. You read the 7, the +, and the 5. But you can’t do anything with them. The multiplication operation must happen first. Evaluating expressions requires you to find the operation with the highest precedence, which can be challenging given parentheses and the need to scan the whole expression.
An alternative form was used by some early calculators. Instead of using infix notation, which places the operators between the operands, these calculators used postfix notation, which places the operators after the operands. The expression above has this postfix form:
A postfix expression can be evaluated in one pass through the sequence of tokens. With your neighbors, design an algorithm in pseudocode that evaluates a postfix expression.
Exercises
Stack-based Expression Evaluation
Convert the following infix expression to postfix form:
Show the steps of using a stack to evaluate the postfix expression. Show the contents of the stack before and after each operation is performed.
Matching Parentheses
Write pseudocode for an algorithm that checks a string to see if it contains correctly matched pairs of brackets and parentheses. Test your algorithm on the following inputs: [()], [](), [(]), ((, )).
ALGORITHM: checkMatches
INPUT: s - a string containing only the characters
'[', ']', '(' and ')'.
OUTPUT: True if the string contains only correctly
matched brackets and parentheses, False
otherwise.
Queue Using Stacks
Implement the queue ADT using only stacks to store information. Analyze the running time of each operation.
class StackQueue<E>
// ?
StackQueue()
// ?
void enqueue(E item)
// ?
E dequeue()
// ?
Stack Using Queues
Implement the stack ADT using only queues to store information. Analyze the running time of each operation.
class QueueStack<E>
// ?
QueueStack()
// ?
void push(E item)
// ?
E pop()
// ?
List Using Stacks
Implement the list ADT using only stacks to store information. Analyze the running time of each operation.
class StackList<E>
// ?
StackList()
// ?
void insert(E item)
// ?
E remove()
// ?
void moveToPos(int pos)
// ?
TODO
- Submit this week’s muddiest point.
See you next time.
P.S. It’s time for a haiku!
FIFO got more votes
Most-old-first-out had no chance
Too many MOFOs