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

Step 1 — What is an operator "waiting"?

WHAT. An expression like a + b has three pieces: two operands (the things being combined — here a and b) and one operator (the action — here +). We read left to right: a, then +, then b. But at the moment we read +, we have not yet seen b. The + cannot fire yet — it has no right-hand operand.

WHY. This single fact — an operator is read before its second operand arrives — is the whole reason we need a memory. The operator must wait somewhere until its operands are ready. That waiting room is a stack (from Stack — ADT and Implementation).

PICTURE. Below, the + steps off the input line and sits in a holding area. The operands a and b flow straight to the output (they need no waiting — an operand is ready the instant we see it). Only the operator lingers.

Step 2 — Why "just append operators too" fails

WHAT. Suppose we naively appended operators to the output the instant we saw them, exactly like operands. Then a + b → a + b, which is still infix, not postfix. So we already know operators must be delayed. The question is: delayed until when?

WHY. An operator can fire only once both its operands are on the output. For +, the left operand a is already out, but the right operand is whatever expression comes after +. So + must wait until that right-hand side is fully emitted. A stack is the natural holder: we push +, keep scanning, and pop it out to the output at the right moment.

PICTURE. The + is pushed onto the operator stack. We keep reading. b goes to output. Now the right operand exists — nothing bigger is pending — so at the end we pop +. Output becomes a b +.

Step 3 — Two operators fight: precedence enters

WHAT. Now read a + b * c. When we reach *, the stack already holds +. Two operators are now competing. Whose operands finish first? We claim * binds b and c before + gets b. So b * c must be emitted, then +.

WHY THIS TOOL — precedence. We need a rule that says "×/÷ act before +/−". That rule is precedence: a number ranking how tightly an operator grabs its operands (see Operator Precedence and Associativity). We choose precedence over any other tie-breaker because it exactly matches how humans read arithmetic.

WHY don't we pop + when * arrives? Because * is taller ( $2 > 1$ ). A taller operator gets to jump ahead of a shorter one still waiting. So + stays; * is pushed on top.

PICTURE. The stack grows to + * with * on top. Because * sits above +, * will be popped first — emitting b c * before the waiting +. Height on the stack = order of firing.

Worked example

a + b * c → a b c * +

tok	why	stack	output
`a`	operand ready		`a`
`+`	needs right operand, push	`+`	`a`
`b`	operand ready	`+`	`a b`
`*`	`*`(2) > `+`(1): don't pop, push on top	`+ *`	`a b`
`c`	operand ready	`+ *`	`a b c`
end	pop top-down: `*` then `+`		`a b c * +`

Step 4 — The reverse fight: pop before pushing

WHAT. Now read a * b + c. When + arrives, the stack holds *. This time the waiting operator is taller than the newcomer. a * b is complete and must fire before + starts.

WHY. +(1) is shorter than the waiting *(2). A shorter operator may not jump ahead of a taller one that is ready. So before pushing +, we must first pop * to the output. Only then does + go on the stack.

PICTURE. As + approaches, the taller * is ejected downward to the output first — like a heavier ball rolling out before the lighter one is allowed in. Output gains *; then + is pushed onto the now-empty stack.

Step 5 — The tie: equal precedence needs associativity

WHAT. Read a - b + c. Now - and + have the same height (both 1). When + arrives, does the waiting - pop, or stay? Both answers look legal. We must break the tie.

WHY THIS TOOL — associativity. Precedence alone is silent on ties. Associativity answers "for equal operators, which side groups first?" (from Operator Precedence and Associativity). Subtraction is left-associative: a - b + c means (a - b) + c — the left - fires first. So when + arrives, the equal - is already complete on its left and must be popped first.

PICTURE. Two equal-height blocks. The left-associative arrow curves left, so the older - is emitted before + enters. If we didn't pop, we'd wrongly compute a - (b + c).

Step 6 — The right-associative exception: `^`

WHAT. Read a ^ b ^ c. Both ^ have equal height (3). Does the waiting ^ pop when the second ^ arrives? For +/- we said yes. For ^ the answer is NO.

WHY. ^ is right-associative: $2^{3^{2}} = 2^{(3^{2})} = 2^{9}$ , not $(2^{3})^{2}$ . The right exponent groups first, so the newer ^ must fire before the older one. Therefore we do not pop the equal ^ — it stays and waits. Look back at the completed condition in Step 5: the second clause requires $o$ to be left-associative. Since ^ is right-associative, that clause is false, so no pop. The rule already handles this — no special case needed.

PICTURE. Two equal ^ blocks, but the arrow curves right: the newer ^ stacks on top of the older one, so the newer fires first.

Worked example

a ^ b ^ c → a b c ^ ^

tok	why	stack	output
`a`	operand		`a`
`^`	push	`^`	`a`
`b`	operand	`^`	`a b`
`^`	equal prec, `^` right-assoc: do NOT pop, push on top	`^ ^`	`a b`
`c`	operand	`^ ^`	`a b c`
end	pop top-down		`a b c ^ ^`

Step 7 — Degenerate case: parentheses override everything

WHAT. Read (a + b) * c. Precedence says * is taller than +, so normally + waits and * jumps ahead. But the parentheses force a + b first. How does the stack obey?

WHY. A ( is a wall: nothing above it may be popped by a normal operator. We push ( as a marker. Operators inside pile on top of it. When the matching ) arrives, we flush everything down to the (, then discard the ( — this is the same LIFO matching from balanced parentheses. The wall guarantees the inner group is fully emitted before anything outside touches it.

PICTURE. ( sits at the bottom as a solid wall (drawn yellow). + rests on it. When ) comes, we pop down to the wall, emit +, and remove the wall. Then * proceeds on an empty stack.

Worked example

(a + b) * c → a b + c *

tok	why	stack	output
`(`	push wall	`(`
`a`	operand	`(`	`a`
`+`	nothing poppable above `(`, push	`( +`	`a`
`b`	operand	`( +`	`a b`
`)`	flush to `(`: pop `+`; discard `(`		`a b +`
`*`	empty stack, push	`*`	`a b +`
`c`	operand	`*`	`a b + c`
end	pop `*`		`a b + c *`

The one-picture summary

Every incoming operator asks the stack top one question: "Are you ready to fire before me?" — and precedence + associativity answer it. Operands stream straight out; ( is an unbreakable wall; ) flushes to that wall. That is the entire algorithm.

Recall Feynman: the whole walkthrough in plain words

Reading left to right, operands are done the moment you see them, so shove them onto the output. Operators are only half-done — they still need their right-hand side — so they wait on a stack. When a new operator shows up, it looks at whoever is already waiting on top: "Are you taller (higher precedence) than me? Or the same height but you group first (left-associative)?" If yes, that waiting operator is actually ready, so it leaves and joins the output before the newcomer sits down. If the newcomer is taller, it just stacks on top and jumps the queue. Exponent ^ is the odd one: it groups from the right, so equal ^s pile up and the newest fires first. Parentheses are walls — push (, and when ) arrives, dump everything down to the wall and throw the wall away. At the very end, drain the stack. The order things hit the output is the order a machine will execute them — that's postfix.

Connections

Stack — ADT and Implementation — the push/pop/top used on every step
Operator Precedence and Associativity — the height and grouping rules derived in Steps 3–6
Postfix Evaluation Algorithm — what the output feeds into next
Expression Trees and Evaluation — the tree these rules implicitly build
Recursion and the Call Stack — the same LIFO idea for function calls
Queues — contrast: FIFO, where the first in leaves first