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

Before you start, hold three anchor ideas in mind (each was built in the parent):

LIFO = Last-In-First-Out: the last thing you opened is the first thing you must close. That is literally what "nesting" means, which is why a stack fits.
Precedence = which operator "grabs its operands first" ( ^ before × ÷ before + − ). Associativity = the tie-breaker when two operators are the same strength: left means "the earlier one goes first", right means "the later one goes first".
A stack frame = the little box of memory a function gets each time it is called (its return address, parameters, locals). Calling pushes a box; returning pops it.

Related builds you may want open: Stack — ADT and Implementation, Operator Precedence and Associativity, Recursion and the Call Stack, Postfix Evaluation Algorithm.

True or false — justify

Every answer here must survive a reason, never a bare "true/false".

True or false: If a bracket string has equal numbers of ( and ), it is balanced.

False. Counts ignore order. )( has one of each yet the closer arrives before any opener, so the stack is empty when ) is read — instant fail.

True or false: If the operator stack is empty at the end of an infix→postfix scan, the expression was well-formed.

False. An empty operator stack only means all operators were flushed to output. A leftover ( on the stack (never matched by a )) is what signals a broken expression — and here it would have been popped as garbage, so you must check the ( case, not just emptiness.

True or false: In {[()]} the closer ] is checked against the bottom of the stack.

False. It is checked against the top. LIFO means the most recently pushed opener ([) is the only one allowed to close now, and it sits on top.

True or false: For + and − (same precedence, left-associative), when a new + arrives you should leave the waiting − on the stack.

False. Left-associativity means the earlier operator acts first, so the waiting − must be popped to output before pushing +. That is why a − b + c becomes a b − c +, i.e. (a−b)+c.

True or false: For ^ (right-associative), an incoming ^ should pop the equal-precedence ^ already on the stack.

False. Right-associativity means the later ^ acts first, so you do not pop the equal ^; you push on top. That gives 2 3 2 ^ ^, evaluating

2^{(3^{2})} = 2^{9}

True or false: The function called last is the one that returns last.

False. It returns first. A caller is frozen until its callee finishes, so the deepest (most recent) call unwinds first — pure LIFO.

True or false: Postfix expressions need parentheses to preserve grouping.

False. Postfix encodes order in the position of operators, so grouping is implicit. a b + c * already means (a+b)*c with no brackets required.

True or false: A queue (FIFO) would work just as well as a stack for matching brackets.

False. A queue returns the first opener first, but nesting demands the last opener first. See Queues for the FIFO contrast — it is the wrong order for nested structure.

Spot the error

Each item states a claim or a trace step that contains one specific mistake. Name it.

([)] — "The counts of each bracket type match, so it's balanced." Where is the flaw?

When ) is read, the stack top is [, not (. The ) wants to close (, but [ was opened later and is still open — the groups cross, violating nesting. Matched counts don't imply correct order.

Trace for ((( : "push, push, push, done — balanced." Where is the flaw?

The final emptiness check is missing. Three openers remain on the stack, i.e. three unfulfilled promises, so it is unbalanced. End condition is stack empty, not no errors during scan.

Converting a + b * c: "when * arrives, pop + first because + is already waiting." Where is the flaw?

You only pop the top when it has higher or equal-with-left-assoc precedence. * is higher than +, so + must wait — b*c happens first. Popping + here would wrongly give a b + c *.

Trace for ) in (a+b)*c: "on ), pop the ( to the output." Where is the flaw?

The ( is discarded, never sent to output. You pop operators to output until you hit (, then throw the ( away. Parentheses vanish in postfix.

fact(n): return n * fact(n-1) with no if n==0 — "it's fine, recursion handles it." Where is the flaw?

There is no base case, so calls never stop pushing frames: fact(3), fact(2), fact(1), fact(0), fact(-1)… forever → stack overflow. Every recursion needs a reachable stopping case.

"In infix→postfix, an operand should be pushed onto the operator stack." Where is the flaw?

Operands go straight to the output, never onto the operator stack. Only operators and ( live on that stack, waiting for their precedence turn.

Why questions

These probe the reason a stack is the right tool, not just the mechanics.

Why does a stack — and not a plain counter — correctly detect crossing like ([)]?

A counter only knows how many are open, not which type is innermost. The stack remembers the identity and order of open brackets, so it can check that the closer matches the current top.

Why must a low-precedence operator "wait" on the stack while a higher one is processed?

Higher precedence means it binds its operands first, so it must reach the output earlier. Making the low operator wait, then popping it after, produces the correct evaluation order for Postfix Evaluation Algorithm to consume left-to-right.

Why does ) "flush" everything down to the matching (?

The parentheses declare an isolated sub-expression that must be fully resolved before anything outside it acts. Flushing to output up to ( emits that whole group first, exactly as the brackets demand.

Why is the call stack LIFO rather than FIFO?

Because a caller is paused mid-execution and must resume exactly where it stopped once its callee returns. The most recently started call is the one currently running and must finish first — that is LIFO by nature. See Recursion and the Call Stack.

Why can converting recursion to iteration prevent a stack overflow?

Deep recursion stores one frame per level in limited stack memory. An explicit loop (or an explicit heap-backed stack) reuses a fixed amount of stack space, so depth no longer consumes call-stack frames.

Why does associativity only matter for equal-precedence operators?

When precedences differ, the higher one already wins unambiguously. Associativity is the tie-breaker used only when two operators are equally strong and we must decide which acts first — see Operator Precedence and Associativity.

Edge cases

The scenarios the naive algorithm forgets. Cover them and you never hit a surprise.

Edge case: the empty string "" for balanced parentheses — balanced or not?

Balanced. No opener means no unfulfilled promise; the stack ends empty, which is the success condition.

Edge case: a closer arrives when the stack is already empty, e.g. first char is ).

Immediate fail. There is no opener to pop and match, so the closer has no partner. This is the guard "if stack empty on a closer → fail".

Edge case: an infix expression that is a single operand like a.

Output is just a. The operand goes to output, no operators are ever pushed, and end-of-scan pops nothing — a valid, trivial postfix.

Edge case: nested parentheses with no operators, like ((a)).

Each ( is pushed and each ) flushes down to its matching ( (finding no operators to emit) and discards it. Output is simply a — redundant brackets disappear.

Edge case: right-associative chain a ^ b ^ c.

Both ^ are pushed without popping each other, giving a b c ^ ^ =

a^{(b^{c})}

. If you had popped the first ^, you'd wrongly get (a^b)^c.

Edge case: mixed left/right at equal-looking moments, a ^ b + c.

When + arrives, the top is ^ (higher precedence), so ^ is popped first: a b ^ c +. Precedence overrides associativity because the operators differ.

Edge case: fact(0) — the base case itself.

It pushes exactly one frame, returns 1 immediately without recursing, and pops. This is the floor that lets the whole recursion unwind; without a reachable base case the stack never shrinks.

Edge case: a balanced string that is also deeply nested, like (((((...))))) a million deep.

The bracket-matcher handles it fine (the stack just grows and shrinks), but if you wrote it as recursion instead, the same depth could exhaust the call stack — matching depth and call depth are different resources.

Connections

Stack — ADT and Implementation — the push/pop operations every trap above relies on.
Operator Precedence and Associativity — the rulebook behind the precedence traps.
Recursion and the Call Stack — frames, base cases, overflow.
Postfix Evaluation Algorithm — why the waiting-operator ordering matters.
Expression Trees and Evaluation — the grouping that postfix encodes implicitly.
Queues — the FIFO contrast that fails on nesting.