🧱 Unit 1 – Data Structures & Algorithms · Lesson 10
Infix to Postfix & Evaluation
Infix, prefix and postfix
In infix the operator is between operands (A + B) – the way we write maths. In prefix (Polish) it comes before (+ A B); in postfix (Reverse Polish) it comes after (A B +).
| Infix | Prefix | Postfix |
|---|---|---|
| A + B | + A B | A B + |
| A + B * C | + A * B C | A B C * + |
| (A + B) * C | * + A B C | A B + C * |
Why postfix?
A computer can evaluate postfix in one left-to-right scan using a stack, with no brackets and no need to remember precedence. Compilers and calculators convert infix to postfix internally.
Precedence & associativity
| Operator | Precedence | Associativity |
|---|---|---|
| ^ | Highest (3) | Right to left |
| * / | 2 | Left to right |
| + - | Lowest (1) | Left to right |
Conversion rules
- 1Operand (A, B, 5…) → write it to postfix
- 2'(' → push on stack
- 3')' → pop and write until '(' is found; discard '('
- 4Operator → pop and write while top has higher or equal precedence (except ^), then push it
- 5End of expression → pop and write everything left
Step-by-step trace
Python
# Trace table for converting A+B*C-D
expr = 'A+B*C-D'
prec = {'+': 1, '-': 1, '*': 2, '/': 2}
stack, out = [], ''
print('Symbol Stack Postfix')
for ch in expr:
if ch.isalpha():
out += ch
else:
while stack and prec[stack[-1]] >= prec[ch]:
out += stack.pop()
stack.append(ch)
print(ch.ljust(7), ''.join(stack).ljust(7), out)
while stack:
out += stack.pop()
print('end'.ljust(7), ''.ljust(7), out)Symbol Stack Postfix
A A
+ + A
B + AB
* +* AB
C +* ABC
- - ABC*+
D - ABC*+D
end ABC*+D-
Python: infix to postfix
Python
def precedence(op):
if op == '^':
return 3
if op in '*/':
return 2
if op in '+-':
return 1
return 0
def infix_to_postfix(expr):
stack, out = [], []
for ch in expr.replace(' ', ''):
if ch.isalnum(): # operand goes straight to output
out.append(ch)
elif ch == '(':
stack.append(ch)
elif ch == ')':
while stack[-1] != '(':
out.append(stack.pop())
stack.pop() # throw away '('
else: # operator
while (stack and stack[-1] != '(' and
(precedence(stack[-1]) > precedence(ch) or
(precedence(stack[-1]) == precedence(ch) and ch != '^'))):
out.append(stack.pop())
stack.append(ch)
while stack:
out.append(stack.pop())
return ''.join(out)
for e in ['A+B*C', '(A+B)*C', 'A*B+C/D', 'A+B*(C-D)/E', 'A^B^C']:
print(e.ljust(12), '->', infix_to_postfix(e))A+B*C -> ABC*+
(A+B)*C -> AB+C*
A*B+C/D -> AB*CD/+
A+B*(C-D)/E -> ABCD-*E/+
A^B^C -> ABC^^
Evaluating postfix
- 1Operand → push it
- 2Operator → pop B (top), pop A
- 3Compute A op B and push the result
- 4At the end the only value left is the answer
Python
def eval_postfix(tokens):
stack = []
for t in tokens.split():
if t.isdigit():
stack.append(int(t))
else:
b = stack.pop() # second operand (top)
a = stack.pop() # first operand
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
elif t == '/': stack.append(a / b)
print('apply', a, t, b, '-> stack', stack)
return stack.pop()
print('Result:', eval_postfix('5 6 2 + * 12 4 / -'))apply 6 + 2 -> stack [5, 8]
apply 5 * 8 -> stack [40]
apply 12 / 4 -> stack [40, 3.0]
apply 40 - 3.0 -> stack [37.0]
Result: 37.0
Practice
- Convert (A+B)*(C-D) to postfix. Answer: AB+CD-*
- Evaluate 2 3 4 * + 5 -. Answer: 9
- Convert A/B-C*D+E. Answer: AB/CD*-E+
Frequently Asked Questions
What is postfix notation?
Operators are written after their operands, for example AB+ instead of A+B. It needs no brackets and no precedence rules to evaluate.
Which data structure is used to convert infix to postfix?
A stack holds operators and brackets until they can be written to the output.
While evaluating postfix, which operand is popped first?
The second (right) operand is popped first, then the first (left) operand; this matters for - and /.
