Stack applications — balanced parentheses, infix-to-postfix, function call stack: Exercises

Definition Notation used everywhere on this page

A stack is a vertical pile written left→right as bottom ... top. The top is the item added most recently — the only one you may pop (remove) or read next.
LIFO = Last-In-First-Out: the item pushed most recently is the one popped first. This is exactly the "close the most recently opened thing first" rule — it will justify almost every step below.
push x means "place x on top". pop means "remove the top item and look at it".
Output (in conversion problems) is the growing postfix string, read left→right.
Opener = one of ( [ {. Closer = one of ) ] }. Each closer matches exactly one opener shape.
Operators are written in code font throughout: ^ (power), * (times), / (divide), + (plus), - (minus). We use these plain code symbols everywhere so there is never a second set of symbols to track.
Precedence (how "strong" an operator is): ^ = 3, then * and / = 2, then + and - = 1. Higher = grabs its operands sooner.
Associativity = tie-breaker when two operators share precedence. + - * / are left-associative (do the left one first); ^ is right-associative (do the right one first).

Figure — Stack applications — balanced parentheses, infix-to-postfix, function call stack

The picture above is your mental model for the whole page: a stack only ever changes at its top, so the last thing in is the first thing out — the meaning of LIFO. Every trace table below is just this pile growing and shrinking one row at a time.

Level 1 — Recognition

You are asked only to classify or read off a result. No long trace needed, but you must justify it with the rule.

Exercise 1.1

Is the string (){}[] balanced? Answer yes/no and say why in one sentence.

Recall Solution 1.1

Yes. Every opener is immediately closed by its own matching shape, so the stack goes push ( → pop ( → push { → pop { → push [ → pop [, ending empty. Two conditions for success both hold: every closer matched the popped opener, and the stack is empty at the end.

Exercise 1.2

For the expression a b + (postfix), which operator acts, and on which two operands?

Recall Solution 1.2

The + acts on a and b, giving a + b. Why: in postfix, an operator uses the two most recent operands to its left — here a and b. There are no precedence or bracket rules to consult; the position is the order.

Exercise 1.3

In infix→postfix, what single action do you take when the current token is an operand (a letter or number)?

Recall Solution 1.3

Append it straight to the output. Operands never wait on the operator stack — only operators need to wait for a chance to run, so operands flow directly to the result.

Level 2 — Application

Run the full algorithm and produce the trace.

Exercise 2.1

Trace the balanced-parentheses check on [{()}]. Balanced or not? Show the stack after each character. Also state: is the empty string "" balanced?

Recall Solution 2.1

char	action	stack (bottom→top)
`[`	push	`[`
`{`	push	`[ {`
`(`	push	`[ { (`
`)`	pop `(` ✓	`[ {`
`}`	pop `{` ✓	`[`
`]`	pop `[` ✓	(empty)

End: stack empty → BALANCED. Each closer meets the most recently opened bracket, which is exactly its partner — that is Last-In-First-Out (LIFO) nesting working correctly.

Empty string "": it is balanced. There are no characters to process, so the stack starts empty and ends empty — both success conditions (nothing mismatched, stack empty at the end) hold vacuously. This is the degenerate base case: "no promises made, no promises broken."

Exercise 2.2

Convert a * b + c to postfix. Show the operator stack and output at each step.

Recall Solution 2.2

tok	action	stack	output
`a`	output		`a`
`*`	push (empty stack)	`*`	`a`
`b`	output	`*`	`a b`
`+`	top `` has higher prec → pop ``; then push `+`	`+`	`a b *`
`c`	output	`+`	`a b * c`
end	pop all		`a b * c +`

Answer: a b * c +. Why pop * when + arrives? * is stronger, so a*b must complete before the weaker + can use its result.

Exercise 2.3

Evaluate the postfix expression 5 1 2 + 4 * + using an operand stack.

Recall Solution 2.3

tok	action	operand stack
`5`	push	`5`
`1`	push	`5 1`
`2`	push	`5 1 2`
`+`	pop 2,1 → `1+2=3` push	`5 3`
`4`	push	`5 3 4`
`*`	pop 4,3 → `3*4=12` push	`5 12`
`+`	pop 12,5 → `5+12=17` push	`17`

Answer: 17. Note operators always take the top two, and the deeper operand is the left argument (5 + 12, not 12 + 5) — this matters for - and /.

Level 3 — Analysis

Now the traps hide in precedence, associativity, and mismatches. You must reason about why the rule fires.

Exercise 3.1

Convert a - b + c to postfix. Both - and + share precedence 1 — decide carefully whether - pops when + arrives.

Recall Solution 3.1

tok	action	stack	output
`a`	output		`a`
`-`	push	`-`	`a`
`b`	output	`-`	`a b`
`+`	top `-` has equal prec and `+` is left-assoc → pop `-`; push `+`	`+`	`a b -`
`c`	output	`+`	`a b - c`
end	pop all		`a b - c +`

Answer: a b - c +. Why pop the equal -? Left-associativity means a - b + c = (a - b) + c; the left operation must finish first, so - comes out before + goes on.

Exercise 3.2

Convert 2 ^ 3 ^ 2 to postfix. ^ has precedence 3 and is right-associative.

Recall Solution 3.2

tok	action	stack	output
`2`	output		`2`
`^`	push	`^`	`2`
`3`	output	`^`	`2 3`
`^`	top `^` is equal prec but `^` is right-assoc → do NOT pop; push	`^ ^`	`2 3`
`2`	output	`^ ^`	`2 3 2`
end	pop all		`2 3 2 ^ ^`

Answer: 2 3 2 ^ ^. Evaluating: 3 2 ^ = 9, then 2 9 ^ = 512. This matches $2^{(3^{2})} = 2^{9} = 512$ , the right-associative reading — exactly why we did not pop the equal ^.

Exercise 3.3

Is ([)] balanced? Show precisely at which character the check fails and why.

Recall Solution 3.3

char	action	stack
`(`	push	`(`
`[`	push	`( [`
`)`	pop → top is `[`, but `)` needs `(` → MISMATCH	—

Not balanced. Fails at the ). Why: ) wants to close (, but [ was opened after ( and is still open on top. Closing ( now would leave [ "crossing" the ), violating proper nesting. The stack catches this because the top is the only bracket allowed to close.

Level 4 — Synthesis

Combine multiple mechanisms in one problem.

Exercise 4.1

Convert a + b * c - d / e to postfix. Show the full trace.

Recall Solution 4.1

tok	action	stack	output
`a`	output		`a`
`+`	push	`+`	`a`
`b`	output	`+`	`a b`
`*`	`*`>`+` → don't pop; push	`+ *`	`a b`
`c`	output	`+ *`	`a b c`
`-`	``>`-` → pop ``; then `+`= `-`, left-assoc → pop `+`; push `-`	`-`	`a b c * +`
`d`	output	`-`	`a b c * + d`
`/`	`/`>`-` → don't pop; push	`- /`	`a b c * + d`
`e`	output	`- /`	`a b c * + d e`
end	pop all (`/` then `-`)		`a b c * + d e / -`

Answer: a b c * + d e / -. Check by grouping: (a + b*c) - (d/e) — the * and / bind their neighbours first, and the two equal-level additive ops resolve left-to-right.

Exercise 4.2

Convert (a + b) * (c - d) ^ e to postfix. Watch how ) flushes and how ^ binds tighter than *.

Recall Solution 4.2

tok	action	stack	output
`(`	push	`(`
`a`	output	`(`	`a`
`+`	push	`( +`	`a`
`b`	output	`( +`	`a b`
`)`	pop to `(` → out `+`, discard `(`		`a b +`
`*`	push	`*`	`a b +`
`(`	push	`* (`	`a b +`
`c`	output	`* (`	`a b + c`
`-`	push	`* ( -`	`a b + c`
`d`	output	`* ( -`	`a b + c d`
`)`	pop to `(` → out `-`, discard `(`	`*`	`a b + c d -`
`^`	`^`>`*` → don't pop; push	`* ^`	`a b + c d -`
`e`	output	`* ^`	`a b + c d - e`
end	pop `^` then `*`		`a b + c d - e ^ *`

Answer: a b + c d - e ^ *. Grouping: (a+b) * ((c-d)^e). The ^ stays above * because it is stronger, so (c-d)^e completes before the multiply.

Level 5 — Mastery

Deep reasoning about the call stack and about designing/breaking inputs.

Exercise 5.1

For fact(4) where fact(n) = if n==0 return 1 else n*fact(n-1), (a) what is the maximum number of frames alive at once, and (b) what value returns first?

Recall Solution 5.1

Calls are pushed in the order fact(4) first, then fact(3), fact(2), fact(1), and finally fact(0) — each new call lands on top. So fact(0) (pushed last) sits at the top, and fact(4) (pushed first) sits at the bottom:

fact(0)  ← top    (pushed LAST, returns FIRST)
fact(1)
fact(2)
fact(3)
fact(4)  ← bottom (pushed FIRST, returns LAST)

(a) Maximum frames alive at once = 5 (for n=4, that is n+1 frames: one per value 4,3,2,1,0). (b) The value returning first is 1, from fact(0) at the top. Then unwinding upward from the top: 1·1·2·3·4 = 24. Each caller was paused awaiting its callee — pure LIFO — so the deepest call resolves first.

Exercise 5.2

Construct the shortest unbalanced bracket string that (i) has an equal number of openers and closers, and (ii) uses only one bracket shape. Explain why it fools the counting test but not the stack.

Recall Solution 5.2

Answer: )( (length 2). Counts: one ) and one ( → equal, so counting says "balanced". The stack disagrees: the first character ) is a closer with an empty stack → immediate fail (there is nothing to pop). It cannot get shorter: length 0 is the empty string (balanced, from Ex 2.1), and any length-1 string has unequal counts. Why the stack wins: it enforces order — a closer must find its opener already open, which counting never checks.

Exercise 5.3

You are given the postfix 3 4 + 5 2 - *. (a) Evaluate it. (b) Reconstruct the equivalent fully-parenthesised infix expression, and explain how the stack of partial expressions builds it.

Recall Solution 5.3

(a) Numeric evaluation:

tok	action	stack
`3`	push	`3`
`4`	push	`3 4`
`+`	`3+4=7`	`7`
`5`	push	`7 5`
`2`	push	`7 5 2`
`-`	`5-2=3` (deeper−top)	`7 3`
`*`	`7*3=21`	`21`

Value = 21. (b) Infix reconstruction — push string operands, and on each operator pop two and wrap them: 3,4 on stack → + → (3+4). Then 5,2 → - → (5-2). Then * pops (5-2) (top) and (3+4) (deeper) → ((3+4)*(5-2)). Answer: ((3 + 4) * (5 - 2)), which evaluates to 7 * 3 = 21, matching (a). The same LIFO stack that computes numbers also assembles the tree of the expression — this is drawn in the figure below.

Read the figure bottom-up: the leaves 3 4 5 2 are pushed as operands, + folds 3 and 4 into (3+4), - folds 5 and 2 into (5-2), and the final * pops both partial expressions and wraps them into the root ((3+4)*(5-2)) — the very reconstruction you traced by hand. See Expression Trees and Evaluation and Postfix Evaluation Algorithm.

Recall Quick self-check answers (all numeric results on this page)

1.1 balanced · 2.1 balanced (and "" empty = balanced) · 2.2 a b * c + · 2.3 = 17 · 3.1 a b - c + · 3.2 2 3 2 ^ ^ = 512 · 3.3 not balanced · 4.1 a b c * + d e / - · 4.2 a b + c d - e ^ * · 5.1 max 5 frames, first return 1, product 24 · 5.2 )( · 5.3 value 21, infix ((3+4)*(5-2)).

Connections

Stack — ADT and Implementation
Operator Precedence and Associativity
Recursion and the Call Stack
Postfix Evaluation Algorithm
Expression Trees and Evaluation
Queues