Infix to Postfix Conversion
Convert an infix arithmetic expression to its postfix (Reverse Polish) form.
Open on GeeksforGeeks ↗Intuition
Operands go straight to the output because their order never changes. Operators must wait, because whether one is emitted now depends on what comes next — that waiting room is the stack. An operator is popped and emitted as soon as it can no longer be outranked, which is what the precedence comparison decides.
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
Operands out, operators onto the stack
Any alphanumeric character is appended to the output immediately, since operands appear in postfix in the same relative order as in infix. Operators are held on a stack until their operands are known to be complete.
Pop by precedence before pushing
Before pushing an operator, pop and emit every stack operator with greater or equal precedence. Those operators bind at least as tightly and their operands are already complete, so they must be emitted first. It is easy to reuse the same >= comparison for every operator, since that is what correctly pops equal-precedence left-associative operators like + or *. But ^ is right-associative, and >= there pops the previous ^ too eagerly, making a^b^c associate as (a^b)^c instead of the correct a^(b^c). Right-associative operators need a strict > comparison instead.
Brackets as scope markers
Push ( unconditionally; it blocks all popping since nothing outside the bracket may be emitted from inside it. On ), pop and emit until the matching ( appears, then discard both brackets — they never appear in postfix. At the end, drain whatever remains on the stack. O(n) time and O(n) space; each character is pushed and popped at most once.
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.