KOI: Postfix notation

The same expression can be written in several different ways: Some examples:

Tree Infix notation Prefix notation Postfix notation
An abstract syntax tree for the expression 2 + 3 2 + 3 + 2 3 2 3 +
An abstract syntax tree for the expression 2 + 3 * 4 2 + 3 * 4 + 2 * 3 4 2 3 4 * +
An abstract syntax tree for the expression 2 * 3 + 4 2 * 3 + 4 + * 2 3 4 2 3 * 4 +
An abstract syntax tree for the expression 2 * (3 + 4) 2 * (3 + 4) * 2 + 3 4 2 3 4 + *

If you are writing a program that calculates the values of expressions, the program must be more complicated to understand the usual infix notation, than if you use prefix or postfix notation. The reason is that with infix notation, the program must take operator precedence into account. Operator precedence is also called operator priority.

Multiplication has higher precedence than addition, which means that if an expression contains both a multiplication and an addition, the multiplication should be performed first. Look at 2 + 3 * 4 and 2 * 3 + 4 in the table!

Postfix notation is simpler. First, you need a stack, where you can put numbers. To calculate the value of a postfix expression, then look at each operand or operator in turn, from left to right, and do this:

As an example, look at how the stack changes when we calculate the postfix expression 2 3 * 4 +:

Start 2 3 * 4 +
  2 3
2
6 4
6
10

Replay!

Stack
2
Stack
2
3
Stack
3
2
*
Stack
6
4
Stack
4
6
+
Stack
10

And again! (So, which one looks best?)

Stack
2
Stack
2
3
Stack
3
2
*
Stack
6
4
Stack
4
6
+
Stack
10


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) August 20, 2007