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.

page revision: 5, last edited: 31 Aug 2011 03:56