Infix to Postfix —
The stack manages precedence for you.
Infix notation (A + B * C) is how humans write expressions. Postfix notation (A B C * +) is how computers evaluate them — no parentheses needed, no precedence rules required. The Shunting Yard algorithm converts between them using a single stack. Watch each token decide whether to output or wait on the stack based on precedence.
Infix vs Postfix
Infix: operator between operands — A + B. Needs parentheses and precedence rules to evaluate correctly. Postfix (Reverse Polish Notation): operator after operands — A B +. Evaluated left to right with a stack — no parentheses, no precedence lookups. Calculators and compilers use postfix internally because it's trivially evaluated with a single stack pass.
Why the stack manages precedence
When a higher-precedence operator arrives, lower-precedence operators already on the stack must wait — they can't output until all higher-precedence operators above them have been processed. The stack naturally enforces this ordering. On LearnBug you watch each operator push, wait, or pop based on precedence — the algorithm becomes readable rather than mysterious.
Shunting Yard algorithm — 4 rules
Process tokens left to right. Each token follows exactly one of these rules.
Operand (A, B, number) → output immediately
Numbers and variables go straight to the output queue. They never wait on the stack.
Operator (+, -, *, /) → pop higher/equal precedence first
Before pushing, pop all operators with higher or equal precedence from the stack to output. Then push the new operator.
'(' → push onto stack
Left parenthesis pushes without popping anything. It acts as a barrier — operators won't pop past it.
')' → pop until matching '('
Pop and output everything until the matching '(' is found. Discard both parentheses — they don't appear in postfix.
Converting "A + B * C - D"
Precedence: * and / (2) beat + and - (1). Expected postfix: A B C * + D -
Token 'A' → operand → output
Operands go straight to output. No stack interaction.
Token '+' → operator → push (stack empty)
Stack is empty, nothing to pop. Push '+'.
Token 'B' → operand → output
Token '*' → precedence 2 > '+' precedence 1 → push without popping
New operator '*' has higher precedence than '+' on the stack. Don't pop '+' — push '*' on top.
Token 'C' → operand → output
Token '-' → pop '*' and '+' first (both ≥ precedence 1)
'-' has precedence 1. '*' (prec 2) pops first → output. '+' (prec 1, equal) pops next → output. Then push '-'.
Token 'D' → output. End → pop remaining stack
Output 'D'. End of input — pop '-' to output. Final postfix: A B C * + D - ✓
Shunting Yard implementation
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
output = []
stack = []
for token in expression.split():
if token.isalnum(): # operand
output.append(token)
elif token == '(': # left paren
stack.append(token)
elif token == ')': # right paren
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # discard '('
else: # operator
while (stack and stack[-1] != '(' and
precedence.get(stack[-1], 0) >= precedence[token]):
output.append(stack.pop())
stack.append(token)
while stack:
output.append(stack.pop())
return ' '.join(output)
print(infix_to_postfix("A + B * C - D")) # → "A B C * + D -"Time & Space Complexity
Frequently asked questions
What is the difference between infix, postfix, and prefix?
Infix: operator between operands — A + B (human-readable, needs precedence rules). Postfix (RPN): operator after operands — A B + (stack-evaluable, no precedence needed). Prefix (Polish Notation): operator before operands — + A B (used in Lisp). Compilers typically convert infix to postfix or an AST internally for evaluation.
How do you evaluate a postfix expression?
Scan left to right. If operand, push it. If operator, pop two operands, apply the operator, push the result. Final value is the last item on the stack. Example: A B C * + D - → push A, push B, push C, pop B and C apply * push BC, pop A and BC apply + push ABC, push D, pop ABC and D apply -.
Why is postfix used by calculators and virtual machines?
Postfix is evaluated left-to-right in one pass with a stack — no backtracking, no precedence lookups, no parenthesis handling. It's deterministic and O(n). Java's JVM, Python's bytecode compiler, and HP calculators all use postfix (or equivalent stack-based) evaluation internally.
How does the algorithm handle right-associative operators like power (^)?
For left-associative operators, you pop when the stack top has equal or higher precedence. For right-associative operators (like ^), you only pop when the stack top has strictly higher precedence — equal precedence keeps the new operator on top. Change >= to > in the precedence check for right-associative operators.
Is this tested in coding interviews?
Yes — LeetCode 150 (Evaluate Reverse Polish Notation) tests postfix evaluation. LC 224 (Basic Calculator) and LC 227 (Basic Calculator II) require infix evaluation, which typically converts to postfix or uses a similar stack approach. Understanding Shunting Yard makes these calculator problems much more tractable.
Watch the operator stack manage precedence on your expression
Paste an infix expression into LearnBug and see every token push, pop, and output step by step.