This page is the exhaustive drill for the parent note Stack applications . We will not re-teach the ideas from zero — the parent did that. Instead we hunt down every awkward case the three algorithms can throw at you, so no exam or interview surprises you.
Before we start, one reminder in plain words, because we lean on it in every example:
Intuition The single rule we test againstA stack is a pile you can only touch from the top . The last thing you dropped on is the first thing you can pick up — Last In, First Out (LIFO) . Every "trap" below is really the same question: did we respect that top-only rule, and did we finish with an empty pile?
Each algorithm has "obvious" cases and "sneaky" cases. Here is the full grid of what can go wrong. Every cell gets covered by a worked example below (the Ex# tells you which).
#
Algorithm
Case class
What makes it tricky
Covered by
A
Balanced brackets
Empty string (degenerate)Zero characters — is nothing balanced?
Ex1
B
Balanced brackets
Closer before any opener Stack empty when we try to pop
Ex1
C
Balanced brackets
Leftover openers Counts look fine but pile isn't empty
Ex2
D
Balanced brackets
Crossing / wrong type Top of stack ≠ matching opener
Ex2
E
Balanced brackets
Deep valid nesting (limiting)Many pushes, then all pops
Ex3
F
Infix→Postfix
Left-associative equal precedence Must pop the waiting operator
Ex4
G
Infix→Postfix
Right-associative ^ Must NOT pop the equal operator
Ex5
H
Infix→Postfix
Nested parentheses + mixed ops Flush-to-( inside a bigger expression
Ex6
I
Infix→Postfix
Word problem (real world)Translate English → infix → postfix → number
Ex7
J
Call stack
Recursion unwinding (limiting depth)Frames return in reverse order
Ex8
K
Call stack
Exam twist: max stack depth Count peak frames, not total calls
Ex9
"" (nothing) and ) balanced?
Forecast: Guess now — is an empty string balanced? Is a single ) balanced? Write down yes/no before reading on.
Part 1: the empty string "".
There are zero characters to read.
Why this step? The algorithm's loop runs once per character; with none, it never runs.
After the (non-existent) loop, we check: is the stack empty?
Why this step? The success test is "no unfulfilled promises left." We opened nothing, so no promises exist.
Stack is empty → BALANCED .
Part 2: the lone closer ).
Read ). It is a closer, so the rule says: if the stack is empty → fail.
Why this step? A closer must pop its matching opener. There is no opener on the pile.
Stack is empty → FAIL . ) is NOT balanced .
Verify: "" has zero unmatched brackets (trivially true, like 0 = 0). ) has one closer and zero openers — impossible to match. Sanity check: an editor's bracket-matcher happily accepts a blank line but flags a stray ).
The picture below shows the two piles side by side — one ends empty (green thumbs-up in your mind), one hits the red "empty-pile pop."
((( and ([)].
Forecast: Both have some symmetry. Guess which fails and why before reading.
Part 1: (((.
Push (, push (, push (. Stack = ( ( (.
Why this step? Every opener is a promise pushed onto the pile.
String ends. Check: is stack empty? No — three promises unfulfilled.
Why this step? Final emptiness is a separate success condition from matching.
→ NOT balanced.
Part 2: ([)].
Push (. Stack = (.
Push [. Stack = ( [.
Read ). Pop the top → it is [. Does [ match )? No.
Why this step? A closer may only close the most recent opener. The most recent is [, but ) wants (. That mismatch is the "crossing."
→ NOT balanced.
Verify: ((( has openers = 3, closers = 0, so counts differ (3 ≠ 0) — fails even the naive count test. ([)] is the sneaky one: it has one (, one ), one [, one ], so counts of each type match , yet the order is wrong. This is exactly the case that proves counting is not enough — you need the stack's order.
{[()]} and then [](){} balanced? (nested vs. sequential)
Forecast: One is deeply nested, one is flat side-by-side. Guess: do both work?
Part 1: {[()]} (maximally nested).
Push {, [, ( → stack { [ ( (depth grows to 3).
Why this step? Each opener nests inside the previous, so the pile only grows — no pops yet.
Read ) → pop (, matches ✓. Read ] → pop [, matches ✓. Read } → pop {, matches ✓.
Why this step? Closers arrive in the exact reverse order of the openers — the LIFO signature.
Stack empty → BALANCED.
Part 2: [](){} (flat, sequential).
Push [, immediately read ] → pop [ ✓ (stack empty again).
Push (, read ) → pop ✓. Push {, read } → pop ✓.
Why this step? Here depth never exceeds 1 — each pair opens and closes before the next begins.
Stack empty → BALANCED.
Verify: In Part 1 the maximum stack depth = 3 (all three openers alive at once). In Part 2 the maximum depth = 1 . Both are balanced, but this proves depth measures nesting , not length — a key idea we reuse for the call stack in Ex9. Total characters are 6 in each.
a - b + c to postfix.
Forecast: - and + are the same precedence level. Guess the postfix — does the - leave the pile when + arrives, or stay?
Recall the precedence, stated as a formula so nothing is assumed:
prec ( × , ÷ ) = 2 > prec ( + , − ) = 1 + - * / are left-associative (evaluate left→right).
tok
action
stack
output
aoperand → output
a
-push (pile empty)
-a
boperand → output
-a b
+top - has equal precedence AND + is left-assoc → pop - , then push +
+a b -
coperand → output
+a b - c
end
pop all
a b - c +
When + arrives, we compare it to the pile's top -.
Why this step? An arriving operator must ask: "is anything already waiting that should execute before me?"
Equal precedence + left-associative → the older operator wins → pop -.
Why this step? Left-associativity means a - b happens before + c, so - must come out first.
Answer: a b - c +.
Verify: With a=8, b=3, c=2: infix 8 - 3 + 2 = (8-3)+2 = 7. Postfix 8 3 - 2 + → 8-3=5, then 5+2=7. Same number ✓ — left-to-right grouping preserved.
2 ^ 3 ^ 2 to postfix.
Forecast: ^ is right-associative, so 2^3^2 means 2^(3^2) = 2^9 = 512, not (2^3)^2 = 64. Guess whether the first ^ leaves the pile when the second ^ arrives.
tok
action
stack
output
2operand → output
2
^push
^2
3operand → output
^2 3
^top ^ equal precedence but ^ is right-assoc → don't pop ; push
^ ^2 3
2operand → output
^ ^2 3 2
end
pop all
2 3 2 ^ ^
Second ^ compares with the first ^ — same precedence.
Why this step? Same reason as Ex4: check what's waiting.
Because ^ is right-associative, the newer one binds tighter, so the older ^ stays.
Why this step? We want 3^2 (the right side) computed first, so the first ^ must wait.
Answer: 2 3 2 ^ ^.
Verify: Postfix 2 3 2 ^ ^ → 3^2 = 9, then 2^9 = 512. And 2^(3^2) = 2^9 = 512 ✓. Contrast the wrong left-assoc answer 2 3 ^ 2 ^ → 2^3=8, 8^2=64 — proving the pop rule flips the result.
a * (b + c * d) - e to postfix.
Forecast: There is an inner * inside the parentheses and an outer * and -. Guess where each operator lands in the output.
tok
action
stack
output
aoutput
a
*push
*a
(push
* (a
boutput
* (a b
+push (nothing higher under the ()
* ( +a b
coutput
* ( +a b c
*top + is lower precedence → don't pop; push
* ( + *a b c
doutput
* ( + *a b c d
)pop to output until (: pop *, pop +, discard (
*a b c d * +
-top * higher precedence → pop *; then - vs empty → push
-a b c d * + *
eoutput
-a b c d * + * e
end
pop all
a b c d * + * e -
Inside the parentheses, * outranks +, so c*d is built first (a b c d *), then + joins it.
Why this step? Precedence inside a group works exactly like outside — the ( just blocks anything below it from popping across the boundary.
The ) flushes everything down to its (.
Why this step? A group must fully resolve before the surrounding operators act.
The outer * (waiting since token 2) pops when - (lower) arrives.
Why this step? - is weaker, so the stronger waiting * executes first.
Answer: a b c d * + * e -.
Verify: Let a=2, b=3, c=4, d=5, e=1. Infix: 2 * (3 + 4*5) - 1 = 2 * (3+20) - 1 = 2*23 - 1 = 45. Postfix 2 3 4 5 * + * 1 - → 4*5=20, 3+20=23, 2*23=46, 46-1=45 ✓.
Worked example A shop bill: "buy 3 shirts at ₹200 eachplus a ₹150 delivery fee, then apply a flat ₹50 discount." Turn it into an expression, convert to postfix, and evaluate.
Forecast: Guess the final amount before doing the algorithm.
Translate English → infix: 3 * 200 + 150 - 50.
Why this step? "3 shirts at ₹200" is a product; "plus delivery" and "minus discount" are additions/subtractions at the same level.
Convert to postfix (using Ex4's left-assoc rule for +/-):
3 → out; * → push; 200 → out; stack *, out 3 200.+ arrives: top * is higher → pop *; push +. out 3 200 *.150 → out. out 3 200 * 150.- arrives: top + equal precedence, left-assoc → pop +; push -. out 3 200 * 150 +.50 → out; end → pop -. 3 200 * 150 + 50 -Why this step? The +/- must chain left-to-right, so - pops the waiting + (the Ex4 trap).
Evaluate postfix: 3*200=600, 600+150=750, 750-50=700.
Answer: ₹700 .
Verify: Direct infix 3*200 + 150 - 50 = 600 + 150 - 50 = 700 ✓. Units: rupees throughout (a count × price/shirt gives rupees, added to a rupee fee, minus a rupee discount — dimensionally consistent).
Worked example Trace the call stack ofsum(3) where sum(n) = 0 if n==0 else n + sum(n-1).
Forecast: Guess the return value and the order in which frames pop.
The figure shows frames pushed downward, then popping upward with their returned values.
sum(3) calls sum(2) calls sum(1) calls sum(0) — four frames pushed.
Why this step? Each call pauses to wait for the deeper call; a paused function's frame stays on the pile.sum(0) hits the base case, returns 0 first (it was pushed last).
Why this step? LIFO — the last frame added is the first removed.Unwind: sum(1)=1+0=1, sum(2)=2+1=3, sum(3)=3+3=6.
Why this step? Each frame resumes at its n + (…) exactly where it paused, using the returned value.
Answer: sum(3) = 6; pop order is sum(0), sum(1), sum(2), sum(3) — reverse of push order.
Verify: sum(3) = 3+2+1+0 = 6 ✓ (the triangular number 2 3 ⋅ 4 = 6 Recursion and the Call Stack for the general frame mechanics.
f(n) calls g(n) twice in sequence (not nested): f(n){ g(n); g(n); } and g calls no one. If main calls f once, what is the maximum number of frames alive at any instant?
Forecast: There are 1 + 1 + 2 = 4 calls in total. Guess the peak depth — it is not 4.
Timeline of pushes/pops:
main pushed (depth 1).main calls f → push f (depth 2).f calls first g → push g (depth 3), g returns → pop (back to depth 2).f calls second g → push g (depth 3), returns → pop (depth 2).f returns → pop (depth 1). main returns → pop (depth 0).
Why this step? The two g calls are sequential , not nested — the first g fully returns (pops) before the second is pushed.
The highest the pile ever reaches is 3 (main, f, one g).
Why this step? Peak depth counts frames simultaneously alive , which depends on nesting, not the total call count (echoing Ex3's depth-vs-length lesson).
Answer: Maximum depth = 3 , even though 4 calls happen in total.
Verify: Total distinct calls = 1(main) + 1(f) + 2(g) = 4; peak simultaneous frames = 3. They differ precisely because sibling calls reuse the freed space — the same reason [](){} (Ex3) has depth 1 despite 3 pairs.
Recall Quick self-test across all cellsEmpty string "" — balanced? ::: Yes — no unfulfilled promises, stack ends empty.
Why does ([)] fail even with matched counts? ::: The closer ) pops [, which does not match — order/nesting is wrong.
Postfix of a - b + c? ::: a b - c + (pop the equal-precedence left-assoc -).
Postfix of 2 ^ 3 ^ 2? ::: 2 3 2 ^ ^ (right-assoc, do NOT pop the equal ^).
Postfix of a * (b + c * d) - e? ::: a b c d * + * e -.
Peak frames when main→f→(g;g) with g a leaf? ::: 3 (sibling g calls are sequential, not nested).
Mnemonic The two exam traps in one breath"Same level? Pop for plus-minus, keep for power." Left-associative + - * / pop an equal top; right-associative ^ keeps it.
Stack — ADT and Implementation — the push/pop/peek used in every trace above.Operator Precedence and Associativity — the rule that Ex4 and Ex5 hinge on.Postfix Evaluation Algorithm — how the "Verify" steps re-run the RPN with one stack.Recursion and the Call Stack — Ex8's frame unwinding in general.Expression Trees and Evaluation — an alternative view of the same precedence structure.Queues — contrast: FIFO would break every LIFO argument here. 