1.2Stack: LIFO and expression evaluation
The idea
A stack is last in, first out. Infix-to-postfix conversion uses a stack of operators; evaluating postfix uses a stack of numbers.
Think of it like this: A pile of plates: you can only touch the top one.
Why it exists
Recursion, DFS, undo, bracket matching and expression evaluation are all stack stories.
How it works
- Operand: send to the output (or push, when evaluating).
- Operator: pop higher or equal precedence operators (left-associative), then push.
- "(" is pushed, ")" pops until its "(".
- Evaluating postfix: pop the right operand first, then the left.
Worked example: Postfix of a + b * c
a goes out, + waits, b goes out, * has higher precedence so it waits on top, c goes out, then pop * and +: a b c * +.
Now play with it
- →Convert the default expression step by step.
- →Try a^b^c: equal-precedence ^ is not popped.
- read "a": operand a goes straight to the output
- read "+": operator +: pop operators of higher or equal precedence, then push
- read "b": operand b goes straight to the output
- read "*": operator *: pop operators of higher or equal precedence, then push
- read "(": push (
- read "c": operand c goes straight to the output
- read "^": operator ^: pop operators of higher or equal precedence (^ is right-associative, so equal is not popped), then push
- read "d": operand d goes straight to the output
- read "-": operator -: pop operators of higher or equal precedence, then push
- read "e": operand e goes straight to the output
- read ")": pop operators until ( is found
- read "^": operator ^: pop operators of higher or equal precedence (^ is right-associative, so equal is not popped), then push
- read "(": push (
- read "f": operand f goes straight to the output
- read "+": operator +: pop operators of higher or equal precedence, then push
- read "g": operand g goes straight to the output
- read "*": operator *: pop operators of higher or equal precedence, then push
- read "h": operand h goes straight to the output
- read ")": pop operators until ( is found
- read "-": operator -: pop operators of higher or equal precedence, then push
- read "i": operand i goes straight to the output
- end: pop everything left
Postfix: abcd^e-fgh*+^*+i-. Pop while the stack top has higher precedence, or equal precedence for a left-associative operator. ^ is right-associative.
- push 8
- push 2
- push 3
- pop 3 then 2, compute 2 ^ 3 = 8, push 8
- pop 8 then 8, compute 8 / 8 = 1, push 1
- push 2
- push 3
- pop 3 then 2, compute 2 * 3 = 6, push 6
- pop 6 then 1, compute 1 + 6 = 7, push 7
- push 5
- push 3
- pop 3 then 5, compute 5 - 3 = 2, push 2
- pop 2 then 7, compute 7 - 2 = 5, push 5
Scan left to right. Operand: push. Operator: pop the right operand first, then the left, apply, push the result. For ^ and − the order of the two pops matters.
Check yourself
The value of the postfix expression 2 3 * 4 + 5 3 - * is
Exam notes (the dense version)
A stack supports push, pop, peek in O(1). It converts infix to postfix (operator stack with precedence) and evaluates postfix (operand stack). It is also used for recursion, matching brackets, undo and DFS. Postfix needs no brackets and no precedence rules.
Previous year questions: Arrays, Stacks, Queues & Linked Lists (14)
PYQs are grouped by topic, so this is the full set for Arrays, Stacks, Queues & Linked Lists; try the ones that match this subtopic. Open all 14 on the topic page.