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 former could be written "$3 \, 4 \, 5 \times \, -$", which unambiguously means "$3 \, (4 \, 5 \, \times) \, -$" which reduces to "$3 \, 20 \, -$" and then ultimately to "$-17$".

The latter could be written "$3 \, 4 \, - 5 \, \times$" (or $5 \, 3 \, 4 - \, \times$, if keeping the operators at the end), which unambiguously means "$(3 \, 4 \, -) \, 5 \, \times$" in either case.

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:

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