The idea: write each operator after its operands
We usually write infix: the operator sits between its two operands, as in 3 + 4 * 2. To read it you need extra rules: precedence (* before +), associativity (8 - 3 - 2 means (8 - 3) - 2) and brackets to override both. Postfix, also called reverse Polish notation, puts each operator right after its operands: 3 4 2 * +. It needs none of those rules: operators appear in exactly the order they are applied.
Turning infix into postfix needs a stack, and so does evaluating the postfix. This page does both: Dijkstra's shunting-yard algorithm on the left, a value stack on the right.
Shunting-yard: operators wait on a stack
Read the tokens left to right. Numbers never wait: they go straight to the output, in the same order as in the input. An operator cannot go out yet, because its right operand has not been read. So it waits on the operator stack. Before it is pushed, it pops to the output every operator on the stack that must be applied first:
- the top has higher precedence, or
- the top has the same precedence and the incoming operator is left-associative.
At the end of the input, every operator still on the stack is popped, top first.
| operator | precedence | associativity |
|---|---|---|
^ | 3 | right |
* / | 2 | left |
+ - | 1 | left |
In 3 + 4 * 2 the * finds + on top. + binds less tightly, so it stays, and * is pushed on top of it. At the end * comes off first: 3 4 2 * +. (Demos: one token at a time; precedence.) The stack keeps operators in rising precedence from bottom to top; that is the whole trick.
Brackets are bracket matching
A ( is pushed as a wall: no operator pops past it. A ) pops to the output everything above the matching (, because those operators were inside the brackets, and then both brackets are dropped. Postfix has no brackets: ( 3 + 4 ) * 2 becomes 3 4 + 2 *. (Demos: brackets; two bracket pairs.)
This is the same stack that checks whether brackets are balanced. Two things can go wrong:
| input | what happens | error |
|---|---|---|
3 + 4 ) * 2 | the ) empties the stack and finds no ( | too many ) |
( 3 + 4 * 2 | a ( is still on the stack at the end | a ( is never closed |
(Demos: mismatched: '(' never closed; ')' with no '('.)
Left and right associativity
Subtraction is left-associative: 8 - 3 - 2 is (8 - 3) - 2 = 3. When the second - arrives it pops the first one, so the first one is applied first: 8 3 - 2 -. Powers are right-associative: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2) = 2 ^ 9 = 512, not (2 ^ 3) ^ 2 = 64. So the second ^ does not pop the first: 2 3 2 ^ ^. (Demos: left-assoc; right-assoc.)
Evaluating postfix with a value stack
Postfix is evaluated in one pass with a second stack, of values. A number is pushed. An operator pops b (the top, the right operand), then a, and pushes a op b. The order matters for -, / and ^. At the end exactly one value is left: the result.
This is how a stack machine works: the JVM, CPython and WebAssembly run bytecode that is postfix underneath (iload, iload, imul). A compiler gets there by parsing the infix into a tree and emitting it children first; see Inside a Tiny Compiler. HP calculators let people type postfix directly.
Cost
Each token is pushed at most once and popped at most once, so both passes are O(n) time, and the stacks hold at most n tokens. The stacks here are the plain array stack (see also push and pop); a recursive-descent parser does the same job with the call stack instead, as in Recursion to an Explicit Stack.
What the page leaves out
Multi-digit numbers and names (a tokenizer would group them), unary minus (-3 needs its own token, usually with high precedence), function calls such as max(a, b) with commas, building the expression tree instead of the postfix string, error positions and recovery, and other parsing methods (precedence climbing, Pratt parsing) that use the same precedence table.
See where this page fits on the Basics mind map.