Postfix Expressions

What is Postfix Form?

When a mathematical expression is written in postfix form, operators follow their operands; for instance, to add $3$ and $4$, one would write "$3 \, 4 \, +$" rather than "$3 + 4$".

If there are multiple operations, the operator is given immediately after its last operand; so the expression written "$3 - 4 + 5$" in conventional notation (which is also called infix notation) would be written "$3 \, 4 - 5 \, +$" in postfix form: $4$ is first subtracted from $3$, then $5$ added to it. Note, this means the operands to the first operator (reading left to right) are to its immediate left.

An advantage of postfix form is that it eliminates the need for parentheses that are required by infix notation (where operators come between their operands). While "$3 - 4 \times 5$" can also be written "$3 - (4 \times 5)$", that means something quite different from "$(3 - 4) \times 5$".

In postfix, the first expression ("$3 - 4 \times 5$") can be written "$3 \, 4 \, 5 \times \, -$", which unambiguously means "$3 \, (4 \, 5 \, \times) \, -$" which reduces to "$3 \, 20 \, -$" and then ultimately to "$-17$".

The expression "$(3 - 4) \times 5$", on the other hand could be written "$3 \, 4 \, - 5 \, \times$", or alternatively as "$5 \, 3 \, 4 - \, \times$", if there was a desire to keep the operators at the end. In both cases, one ends up with the product of $-1$ and $5$.

Postfix notation is also called Reverse Polish Notation (RPN).

Using a Stack to Evaluate a Postfix Expression

The algorithm for evaluating any postfix expression with a stack is fairly straightforward:

While there are input tokens left, read the next token and then do one of two things:
- If the token is a value, push it onto the stack.
- Otherwise, the token is an operator (operator here includes both operators and functions), so we do the following:
  - Presuming the operator takes $n$ arguments, pop the top $n$ values from the stack.
  - Apply the operator to these $n$ values.
  - Push the result(s), if any, back onto the stack.
When there is no more input, there should only be one value in the stack -- that value is the result of the calculation.

As an example: the infix expression "$5 + ((1 + 2) \times 4) - 3$" when written in postfix is given by the following:

$$5 \, 1 \, 2 + 4 \, \times \, + \, 3 \, -$$

To evaluate this postfix expression, we read the above from left-to-right. The state of the stack after each input element is examined is shown below. The "bottom" of the stack is the left-most element, while the right-most element is on the stack's "top".

Input   Action         Stack     Details
  5     push value     5
  1     push value     5 1
  2     push value     5 1 2
  +     add            5 3       pop 2, pop 1, push 1+2=3
  4     push value     5 3 4
  x     multiply       5 12      pop 4, pop 3, push 3x4=12
  +     add            17        pop 12, pop 5, push 5+12=17
  3     push value     17 3      
  -     subtract       14        pop 3, pop 17, push 17-3=14

Upon reaching the end of the input, we pop the last element on the stack.
This element is the result of evaluating the expression: 14