Postfix notation

This notation is called postfix because the rule is operator afteroperand(s). Parentheses are not needed. The notation we normally use is called infix. If you start with an infix expression, the following algorithm will give you the equivalent postfix expression.

• Variables and constants are left alone.
• E op F becomes E' F' op, where E' and F' are the postfix of E and F respectively.
• ( E ) becomes E', where E' is the postfix of E.

One question is, given say 1+2-3, what is E, F and op? Does E=1+2, F=3, and op=+? Or does E=1, F=2-3 and op=+? This is the issue of precedence mentioned above. To simplify the present discussion we will start with fully parenthesized infix expressions.

Example: 1+2/3-4*5

1. Start with 1+2/3-4*5
2. Parenthesize (using standard precedence) to get (1+(2/3))-(4*5)
3. Apply the above rules to calculate P{(1+(2/3))-(4*5)}, where P{X} means “convert the infix expression X to postfix”.
4. P{(1+(2/3))-(4*5)}
5. P{(1+(2/3))} P{(4*5)} -
6. P{1+(2/3)} P{4*5} -
7. P{1} P{2/3} + P{4} P{5} * -
8. 1 P{2} P{3} / + 4 5 * -
9. 1 2 3 / + 4 5 * -

Example: Now do (1+2)/3-4*5

1. Parenthesize to get ((1+2)/3)-(4*5)
2. Calculate P{((1+2)/3)-(4*5)}
3. P{((1+2)/3) P{(4*5)} -
4. P{(1+2)/3} P{4*5) -
5. P{(1+2)} P{3} / P{4} P{5} * -
6. P{1+2} 3 / 4 5 * -
7. P{1} P{2} + 3 / 4 5 * -
8. 1 2 + 3 / 4 5 * -