Convert Infix to Postfix Using a Stack
The stack is the whole trick. It holds operators that cannot be written down yet because something stronger might still be coming. Press play below and watch it fill and drain, one token at a time.
Interactive stack visualiser
Operator stack
Postfix output
READY Press Play, or step through one token at a time.
Full stack trace
| # | Token | Stack action | Stack | Postfix output |
|---|
Use ← and → to step once the visualiser has focus.
Why a stack, and not something else
When you read A + B * C left to right and reach the +, you
cannot write it down yet. You do not know whether the thing after B will
be weaker than + (in which case + goes out now) or stronger
(in which case it has to wait). So the + has to be held.
And when several operators are held at once, the one you always release first is the most recent one — because it is the innermost, most tightly bound. Last in, first out. That is precisely a stack, which is why converting infix to postfix using a stack is not merely one approach among many; it is the natural fit for the problem.
Operands are never in doubt, so they go straight out. Operators are always in doubt, so they wait on the stack until something proves it is their turn.
The six stack rules
Every token you read falls into one of six cases. Apply the matching rule and move on — there is nothing else to decide.
- Operand (a letter or number) Append it to the output immediately. It never touches the stack.
-
Opening bracket
(Push it. It acts as a floor marker: popping will stop when it is reached. -
Closing bracket
)Pop operators to the output until(is on top, then pop that(and throw both brackets away. -
Operator, stack empty or
(on top Push it. There is nothing above it that could outrank it. -
Operator, weaker than or equal to the top
Pop the top to the output and check again. Keep popping while the condition holds,
then push the new operator. The equal case is what makes
A - B - Ccome out asA B - C -; the exception is^, which is right associative and does not pop its equals. -
End of the expression
Pop everything still on the stack to the output. If a
(turns up here, the expression had unbalanced brackets.
Worked example, stack shown at every step
Converting A + B * C - (D / E). The stack is written left to right with
the top on the right, which is the convention the visualiser above
uses too.
| # | Token | Stack action | Stack | Output |
|---|---|---|---|---|
| 1 | A | Operand → output | empty | A |
| 2 | + | Stack empty → push | + | A |
| 3 | B | Operand → output | + | A B |
| 4 | * | Higher than + → push | + * | A B |
| 5 | C | Operand → output | + * | A B C |
| 6 | - | Pop *, pop +, then push - | - | A B C * + |
| 7 | ( | Push as marker | - ( | A B C * + |
| 8 | D | Operand → output | - ( | A B C * + D |
| 9 | / | Top is ( → push | - ( / | A B C * + D |
| 10 | E | Operand → output | - ( / | A B C * + D E |
| 11 | ) | Pop /, discard the ( | - | A B C * + D E / |
| 12 | end | Pop - | empty | A B C * + D E / - |
Notice step 6. The - is weaker than * and equal to
+, so both come off before it goes on. Students who only pop the strictly
stronger operator get A B C * D E / - + here, which is a different
expression entirely.
Nested brackets
Nesting needs no extra rules. Each ( adds another marker and each
) unwinds down to the nearest one, so the stack simply grows deeper.
Converting ((A + B) * (C - D)) ^ E:
((A + B) * (C - D)) ^ E
( stack: ( (
A + B → A B + flushed when the first ) arrives
* stack: ( *
(C - D) → C D - flushed when the second ) arrives
) pops * output: A B + C D - *
^ E stack: ^ output: A B + C D - * E
postfix: A B + C D - * E ^Load that expression into the visualiser with the nested button above to watch the stack reach three deep and come back down.
Stack operations you need
The algorithm uses four operations, all of them O(1). Any stack implementation works — an array with an integer top, a linked list, or your language's built-in type.
| Operation | What it does | Used for |
|---|---|---|
| push(x) | Add x to the top | Storing an operator or ( |
| pop() | Remove and return the top | Sending a waiting operator to the output |
| peek() | Read the top without removing it | Comparing precedence before deciding |
| isEmpty() | Is the stack empty? | Guarding every peek and pop |
peek() is the one people forget. You have to look at the top
before you commit to popping it, otherwise you cannot compare precedence
without destroying the value.
How large does the stack get?
In the worst case the stack holds n entries for an n-token expression — that happens
with input like ((((a)))) or a long right-associative chain such as
a ^ b ^ c ^ d, where nothing can be released until the very end. Sizing a
fixed array stack at the length of the input string is therefore always safe, and it
is what the C implementation does.
Five mistakes that cost marks
-
Popping only strictly greater precedence.
Equal precedence must also pop, for every left-associative operator. Otherwise
A - B - Ccomes out wrong. -
Treating
^like the others. Exponentiation is right associative, so it is the single exception: it does not pop an equal^. -
Writing brackets into the output.
Postfix has no brackets. A
(is discarded when its)arrives; neither is ever emitted. -
Popping past a
(on a closing bracket. The(is a floor. Stop there, or you will drag operators out of an enclosing sub-expression too early. - Forgetting the final flush. When the input ends, the stack is usually not empty. Everything left on it belongs at the end of the output, popped top-down.
Frequently asked questions
Why is a stack used to convert infix to postfix?
Because an operator read from an infix expression cannot be output immediately — a higher-precedence operator may still follow it. It must be held, and when several are held the most recently pushed one is always released first, since it is the most tightly bound. That last-in-first-out behaviour is exactly what a stack provides.
What is pushed onto the stack during conversion?
Only operators and opening brackets. Operands go straight to the output and never enter the stack. Closing brackets are never pushed either — they trigger popping and are then discarded along with their matching opening bracket.
When do you pop from the stack?
In three situations: when a closing bracket arrives (pop until the matching opening bracket), when an incoming operator has lower or equal precedence than the top (pop while that holds), and when the input is finished (pop everything that remains).
How big should the stack be?
The length of the input expression is always enough. In the worst case — deeply nested brackets, or a chain of right-associative operators — every token could be on the stack at once, but never more than that.
What if the stack still has a "(" on it at the end?
The expression had an unbalanced opening bracket and is invalid. A correct implementation reports an error at that point rather than emitting the bracket into the output.
Can you convert infix to postfix without a stack?
You can — by building an expression tree and reading it in post-order, or by recursive descent parsing. Both are more work and both use a stack implicitly (the call stack, or the tree's structure). For a single left-to-right pass, the explicit stack is the simplest correct method.