Infix to Postfix Conversion
Convert an infix arithmetic expression to its postfix (Reverse Polish) form.
- 1 <= |expression| <= 10⁵
- Operators: + - * / ^ with brackets
- ^ is right-associative, unlike the others
Intuition
Infix to postfix conversion rewrites an ordinary expression like a + b * c into a b c * +, where operators follow their operands. Postfix needs no parentheses and no precedence rules, which is why compilers and calculators use it internally.
The conversion is Shunting-yard, and its organising idea is that operands can be emitted immediately while operators must wait:
- Output operands as they appear; hold operators on a stack until an operator of lower or equal precedence forces them out.
An operand's position in the output is already known, but an operator's is not — it depends on what follows.
On reading an operator, pop from the stack every operator with greater or equal precedence before pushing the new one. That popping is what places higher-precedence operations earlier in the output, so a + b * c keeps * ahead of +.
Associativity changes that comparison. Left-associative operators pop on equal precedence, so a - b - c becomes a b - c -. Right-associative operators like exponentiation must not, or 2 ^ 3 ^ 2 is grouped the wrong way. Using the same rule for both is the standard bug.
Parentheses are handled directly: push (, and on ) pop until the matching ( is found. Neither bracket is ever written to the output — their entire effect is already captured by the ordering they forced.
At the end, pop any operators still on the stack. Forgetting this drops the final operators, which is easy to miss because short test expressions often end with an operand.
The shunting-yard algorithm. Operands pass straight through; operators wait on a stack until something of equal or higher precedence arrives, then pop. Parentheses act as barriers the popping loop refuses to cross, which is what makes grouping work without recursion.
Approach
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(n) space.
Emit operands immediately
An operand's output position is already known, but an operator's depends on what comes after it. That asymmetry is why operators need a stack and operands do not.
Pop before pushing an operator
On reading an operator, pop every stacked operator with greater or equal precedence first. This places higher-precedence operations earlier in the output.
Distinguish associativity
Left-associative operators pop on equal precedence, so a - b - c becomes a b - c -. Right-associative ones like ^ must not, or 2 ^ 3 ^ 2 groups incorrectly.
Push an opening parenthesis
Place ( on the stack as a barrier. Operators above it are enclosed by the group and must be emitted before anything outside it.
Unwind on a closing parenthesis
Pop and output until the matching ( is reached, then discard both. Neither bracket ever appears in the output — their effect lives entirely in the ordering.
Flush the stack at the end
Pop any remaining operators after the input is exhausted. Forgetting this drops the final operators, and short test expressions often hide the bug.
Cost of the conversion
Each token is pushed and popped at most once, giving O(n) time and O(n) space for the stack in the worst case of deep nesting.
Solution & live demo
Common pitfalls
Popping past an opening parenthesis
while st and prec.get(st[-1], 0) >= prec[ch]:
while st and st[-1] != '(' and prec.get(st[-1], 0) >= prec[ch]:( has no precedence and must block the pop loop — it marks where the current group began. Without the guard, operators from an enclosing group get emitted inside the inner one.
Leaving the opening parenthesis on the stack
while st and st[-1] != '(':
out.append(st.pop())while st and st[-1] != '(':
out.append(st.pop())
st.pop()The ( is a marker, not output. Failing to discard it after the group closes leaves it on the stack, where the final drain appends it to the result.
Treating right-associative ^ like the others
prec[st[-1]] >= prec[ch] # for ^ too
# for right-associative operators use > rather than >=
2^3^2 must group as 2^(3^2), so an equal-precedence ^ on the stack should not pop. Using >= uniformly makes exponentiation left-associative and silently changes the meaning.
Edge cases
It is emitted directly and the stack stays empty.
The brackets are consumed and never appear in the output.
^Needs a strict > comparison; using >= produces the wrong association for a^b^c.
Left-associative ones pop on >=, giving the correct left-to-right grouping.