Infix, prefix and postfix

We normally write arithmetic with the operator between its operands, as in x + y. This is infix notation. It needs precedence rules (BODMAS) and parentheses to show the order of operations: in 3 + 4 × 5, multiplication comes first, unless we write (3 + 4) × 5.

The Polish mathematician Jan Lukasiewicz introduced a notation in which the operator comes before its operands: +xy. This is prefix or Polish notation. Its mirror image, with the operator after the operands, xy+, is postfix or reverse Polish notation.

Their great advantage: prefix and postfix expressions need no precedence rules and no parentheses. The order of the symbols itself shows the order of operations, so a computer can evaluate them in a single left-to-right pass. That is why compilers convert infix expressions to postfix.

Converting infix to postfix uses a stack. Read the infix expression from left to right, building a string called postExp:

• An operand goes straight into postExp.
• A left parenthesis ( is pushed onto the stack.
• An operator is pushed onto the stack, but first, any operators on the stack with higher or equal precedence are popped into postExp.
• A right parenthesis ) makes you pop operators into postExp until the matching ( is reached; the ( is discarded.
• At the end, pop any remaining operators into postExp.

So only operators and parentheses ever go onto the stack. For example, (a + b) × c becomes ab+c×, and a + b × c becomes abc×+.