COMP1927 - Applications for Stacks

Postfix, Infix and Prefix calculators are a way of calculating answers to mathematical problems, without brackets (hence relying purely on order of operations).

Postfix Calculators

Postfix takes two numbers and an operation in the format:

3 4 +

and applies the operation to them.

This can get quite complicated, for instance:

(1)
\begin{equation} 2 1 3 + 2 5 * * 7 + * = (2 (((1 3 +) (2 5 *) *) 7 +) *) \end{equation}

The algorithm is explained clearly on wikipedia, however it boils down to the following:

One stack - add numbers to it.

When you hit an operation:

  1. Pop the previous two numbers off
  2. Apply the operation to them
  3. Push the result back on

Infix Calculators

Infix takes two numbers and an operation in the format:

3 + 4

and applies the operation to them.

Two stacks - numbers and operations. Inputs are allocated accordingly.

Whenever a '*' or '/' is encountered:

  • Pop the previous element off the stack
  • Read in the next number
  • Apply the operation to the two numbers
  • Push the result back onto the stack

Once all inputs are read in:

  • Pop off each '+' or '-'
  • Pop the first two elements we read in off (as in, the bottom of the stack, not the top)
  • Apply the operation to the first two elements
  • Push their result back on

Prefix Calculators

Prefix takes two numbers and an operation in the format:

+ 3 4

and applies the operation to them.

Read the input right to left and then apply postfix to it.