teaching machines

CS 240: Lecture 13 – Stacks and Queues Continued

September 22, 2021 by Chris Johnson. Filed under cs3, fall-2021, lectures.

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.

Sincerely,

P.S. It’s time for a haiku!

FIFO got more votes
Most-old-first-out had no chance
Too many MOFOs