Postfix Expressions

In most programming languages, mathematical expressions are written with the operator between the two operands, as in 1+2. This format is called infix. An alternate format used by some calculators is called postfix. In postfix, the operator follows the operands, as in 1 2+.

The reason postfix is sometimes useful is that there is a natural way to evaluate a postfix expression using a stack.

• Starting at the beginning of the expression, get one term (operator or operand) at a time.
• If the term is an operand, push it on the stack.
• If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack.
• When we get to the end of the expression, there should be exactly one operand left on the stack. That operand is the result.

As an exercise, apply this algorithm to the expression 1 2 + 3 *.

This example demonstrates one of the advantages of postfix: there is no need to use parentheses to control the order of operations. To get the same result in infix, we would have to write (1 + 2) * 3. As an exercise, write a postfix expression that is equivalent to 1 + 2 * 3?