Stacks for Expressions
A stack remembers what is still pending in the order it must be resolved: the most recent thing first. That is exactly what nested brackets need, since the last opened bracket is the first one that must close. Postfix notation removes the need for brackets altogether, because every operator arrives right after the two values it applies to, so a value stack is all the evaluator needs. Converting infix to postfix, or evaluating infix directly, is the same idea with operators waiting on a stack until something of lower precedence arrives and forces them out.
Convert "3+4*(2-1)" to postfix. Operands go straight to the output. An operator first flushes any operator on the stack with precedence at least its own, then waits on the stack itself. A closing bracket flushes back to its opener.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.
Next is '3'. What happens?
Answer: Straight to the output. Operands never wait.
Next is '+'. What happens?
Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.
Next is '4', top of the operator stack is '+'. What happens?
Answer: Straight to the output. Operands never wait.
Next is '*', top of the operator stack is '+'. What happens?
Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.
Next is '(', top of the operator stack is '*'. What happens?
Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.
Next is '2', top of the operator stack is '('. What happens?
Answer: Straight to the output. Operands never wait.
Next is '-', top of the operator stack is '('. What happens?
Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.
Next is '1', top of the operator stack is '-'. What happens?
Answer: Straight to the output. Operands never wait.
Next is ')', top of the operator stack is '-'. What happens?
Answer: Flush first, then act. Higher or equal precedence operators must come out first to keep the order right.
How it runs, step by step
Convert "3+4*(2-1)" to postfix. Operands go straight to the output. An operator first flushes any operator on the stack with precedence at least its own, then waits on the stack itself. A closing bracket flushes back to its opener.
Infix to postfix conversion of 9 characters.
'3'. An operand goes straight to the output.
Character 3. Output 3, operators empty.
'+'. Nothing to flush, so it waits on the stack.
Character +. Output 3, operators +.
'4'. An operand goes straight to the output.
Character 4. Output 34, operators +.
'*'. '+' on the stack binds looser, so it stays and '*' goes on top.
Character *. Output 34, operators +*.
'('. An opening bracket goes on the stack as a fence: nothing below it can be flushed until it closes.
Character (. Output 34, operators +*(.
'2'. An operand goes straight to the output.
Character 2. Output 342, operators +*(.
'-'. Nothing to flush, so it waits on the stack.
Character -. Output 342, operators +*(-.
'1'. An operand goes straight to the output.
Character 1. Output 3421, operators +*(-.
')'. A closing bracket: - moves to the output. The '(' is discarded.
Character ). Output 3421-, operators +*.
The end of input flushes the remaining operators, *+. Postfix: 3421-*+. Each character is pushed and popped at most once, so the conversion is O(n).
Postfix 3421-*+.
Write it yourself
Define isBalanced(expression) and return true when every bracket closes in the right order. It runs in your browser against this lesson's own 2 examples.
// Push an opening bracket, and a closing one must match what comes off the top. Anything left over at the end is unclosed.function isBalanced(expression) { return false;}
Remember
- Brackets: push openers, and a closer must match the top of the stack. Balanced means the stack ends empty.
- Postfix: push numbers; an operator pops two (the lower one is the left operand) and pushes the result.
- Infix: an operator flushes everything on the stack with precedence at least its own, then waits; brackets fence the stack.
Related
Where this is used
Document formatsPDF page content and PostScript
A PDF page is drawn by a stream of postfix operators, so 1 0 0 1 72 720 cm pushes six numbers and then names the operator that consumes them. Every operator takes a fixed count of operands that are already on the stack, so the renderer needs no precedence table and no lookahead, and it can draw while the stream is still arriving. PostScript, the older format PDF's drawing model grew out of, takes the same design all the way to a programming language, with the operand stack exposed to the program itself.
RuntimesJVM bytecode and WebAssembly
Both are stack machines, so a + b compiles to iload_1, iload_2, iadd, which is postfix. The compiler produces that order by walking the expression tree in post-order, the same rearrangement the infix-to-postfix pass does here, and a stack interpreter can then run it with exactly the postfix loop above, though production engines compile it down to registers instead. Both formats are checked before they run: the JVM verifier and the WebAssembly validator work out the stack's types at every instruction, so each pop is proved in advance to find the operand types it expects.
CompilersBracket errors in the CPython tokenizer
CPython's tokenizer keeps a stack of open brackets together with the line and column where each was opened. That is what lets Python 3.10 and later say which opener a mismatched closer belongs to, instead of pointing vaguely at the end of the file. The same stack decides whether a newline ends a statement: while it is non-empty you are inside brackets, so the line just continues, which is why a list literal can span many lines with no backslashes.
HardwareRPN calculators and Forth
The HP-35 and the HP-12C have no equals key and no brackets: you push operands with ENTER and each operator pops what it needs. On a machine with a few hundred bytes of memory, a value stack plus a pop-per-operator rule is far less hardware than an infix parser carrying a precedence table and a bracket stack. Forth, and the Open Firmware boot environments built on it, made the same trade to stay small enough to live in ROM.
Why it works this way
Why a stack and not a counter
With one kind of bracket a counter is enough: add one for an opener, subtract one for a closer, and it goes negative exactly when a closer arrives too early. With three kinds it fails, because ([)] and ([]) keep the same count at every step and both end at zero. What has to be remembered is not how many brackets are open but which one is innermost, and only the stack holds that.
Why the flush test is >= and not >
That comparison is where associativity lives. In 8/4/2 the second slash arrives while the first is still on the stack at equal precedence, so >= flushes it and you get (8/4)/2 = 1, which is what left-associative division means. Change it to > and the first slash waits its turn, producing 8/(4/2) = 4, while every expression with a single operator still comes out right. Right-associative operators such as exponentiation are the exception and need > for exactly this reason.
The two pops come off in reverse
Taking b before a is not a stylistic choice: the stack hands back the right operand first, because it was pushed last. Swap those two lines and + and * keep giving correct answers while - and / quietly stop, so 5 3 - evaluates to -2 instead of 2. It is a bug that passes half of any test set you throw at it.
Postfix only drops brackets if every operator has a fixed arity
Postfix reads unambiguously because seeing an operator tells you exactly how many values to pop. Unary minus breaks that rule: in 3 - -4 the same character means two different things, and once both are written as a bare - in the output nothing can tell them apart. Real converters give unary minus its own token and decide which one it is from position: a minus that follows another operator or an opening bracket, or that starts the expression, is the unary one.
Read more
- Shunting yard algorithmWikipedia
- Reverse Polish notationWikipedia
- Expression parsingcp-algorithms
- The Structure of the Java Virtual MachineJava Virtual Machine Specification · docs.oracle.com
- Operator-precedence parserWikipedia
Next up
- Sliding Window MaximumA monotonic deque of indices keeps the window maximum at the front in amortized O(1).
- Largest Rectangle in HistogramKeep a stack of rising bars; popping a bar bounds its rectangle by the nearest shorter bars on both sides.
- Next Smaller ElementThe nearest smaller value to the right.