Questions: Stack Applications: Expression Evaluation and Parsing

Question 1

You evaluate the postfix expression '4 2 3 + *' using a stack. What is the result?

• A. 11 — treating the expression as infix: 4 * 2 + 3
• B. 10 — treating it as 4 + 2 * 3
• C. 20 — correctly pushing 4, then computing 2+3=5, then 4*5
• D. 24 — multiplying all three numbers

Answer: (C)

Postfix evaluation: push 4, push 2, push 3. Hit '+': pop 3 and 2, compute 5, push 5. Hit '*': pop 5 and 4, compute 20, push 20. The result is 20. Option A is the classic mistake of reading postfix as infix. The ordering of tokens in postfix explicitly encodes precedence, so no parentheses or rules are needed — operators simply apply to the two most recently pushed operands.

Question 2

In Dijkstra's shunting-yard algorithm, when you encounter an operator with lower precedence than the operator currently at the top of the stack, you:

• A. Push the new operator immediately — precedence is handled at evaluation time
• B. Pop and output the higher-precedence operator first, then push the new operator
• C. Discard the lower-precedence operator since higher-precedence operators take over
• D. Push both and use a tiebreaker rule later

Answer: (B)

The stack in shunting-yard is a holding area for operators waiting to be output. Higher-precedence operators must appear in the output before lower-precedence ones that arrived earlier, because postfix evaluation will apply them first. So when a lower-precedence operator arrives, you flush all higher-precedence operators from the top of the stack to the output before pushing the new one. This reordering encodes precedence into the postfix sequence.

Question 3

Postfix notation is harder for computers to evaluate than infix notation because it requires more stack operations.

• T. True
• F. False

Answer: False

Postfix is actually easier and more natural for computer evaluation. A single left-to-right scan with a stack handles all cases: push numbers, pop and apply operators. No precedence rules, no backtracking, no parenthesis-handling are needed at evaluation time. Infix is harder — it requires either recursive descent parsing or the shunting-yard conversion step first. Postfix is used internally in calculators and stack-based languages precisely because it maps so cleanly to stack operations.

Question 4

A stack is the appropriate data structure for parenthesis matching because the most recently opened delimiter must be the first to close.

• T. True
• F. False

Answer: True

This is exactly the LIFO property of stacks. When you push each opening delimiter and pop when you encounter a closing one, the top of the stack is always the innermost unclosed delimiter — the one that must close next. If you tried to use a queue, you'd check the oldest unclosed delimiter first, which is wrong. The LIFO order directly mirrors the nesting contract of balanced delimiters.

Question 5

Why is a stack — specifically its LIFO property — the natural data structure for evaluating postfix expressions?

Model answer: In postfix, operands arrive before their operator. When an operator appears, it applies to the two most recently pushed operands. 'Most recently pushed' is exactly what the top of a stack provides. LIFO guarantees that popping twice gives you the two most recent values in the correct order. This mirrors the nested structure of expressions: inner sub-expressions produce results before outer operators need them, and the stack holds those intermediate results until they're needed.

The deeper insight is that stacks are the computational model of nesting. Any time a problem involves 'defer this, complete the inner thing, then come back,' a stack captures the state of deferred contexts. Postfix evaluation is the simplest case: each number is a deferred operand pushed onto the stack; each operator collapses the two most recent deferred values. Parenthesis matching, shunting-yard, and recursive descent parsers all apply the same insight to more complex nesting structures.