Source: C Programming – Stack Data Structure MCQs & Short Answers
Tags: postfix evaluation, infix to postfix, shunting yard, expression tracing, stack tracing, depth-first search, DFS, recursion call stack, output tracing, bug tracing, stack debugging, operator precedence, COP 3502
Difficulty: Intermediate Prerequisites: Parts 1 and 2 (Stack Fundamentals and Stack Implementation in C). You need to be comfortable with push/pop mechanics and array-based stack code before attempting expression tracing.
Stacks are not just an exam abstraction. They solve a specific class of problems where you need to process things in reverse order or hold something "for later" while you deal with what is in front of you. This set of notes covers three applied areas: evaluating postfix (reverse Polish) expressions, converting infix expressions to postfix using operator precedence, and finding/fixing bugs in stack code. These topics appear frequently as output tracing and code correction questions on exams.
Postfix expressions are evaluated left to right using a stack: push operands, pop-and-compute when you hit an operator. Infix-to-postfix conversion uses a stack to manage operator precedence. Bug tracing in stack code almost always comes down to pointer mistakes (single vs double pointer) or off-by-one errors in the top variable.
Postfix expression (Reverse Polish Notation, RPN)
A mathematical notation where every operator follows its operands. For example, 5 3 + means "add 5 and 3." No parentheses are needed because the order of operations is unambiguous. In simple terms, instead of writing 5 + 3, you write 5 3 +. The operator comes after.
Infix expression
The conventional notation where operators sit between operands: A + B * C. Requires parentheses or precedence rules to resolve ambiguity.
Operator precedence
The rules governing which operator is applied first in an expression. * and / have higher precedence than + and -. In infix-to-postfix conversion, higher-precedence operators stay on the stack longer before being popped to the output.
Depth-first search (DFS)
A graph traversal algorithm that explores as far as possible along each branch before backtracking. DFS uses a stack (explicitly or via recursion) to remember which nodes to visit next. This is the standard application-level MCQ answer: "Which application commonly uses stacks?" Answer: depth-first search.
Call stack (function call stack)
The system-managed stack that stores function call frames during program execution. Each function call pushes a frame (local variables, return address); each return pops one. This is why infinite recursion causes a stack overflow: the call stack runs out of space.
The algorithm:
Read the expression left to right, token by token.
If the token is a number (operand), push it onto the stack.
If the token is an operator (+, -, *, /), pop two operands from the stack. The first popped value is the right operand, the second is the left operand. Compute the result and push it back.
After the entire expression is processed, the single remaining value on the stack is the result.
Worked example: 5 3 + 8 2 - *
Token | Action | Stack after |
|---|---|---|
5 | Push 5 | [5] |
3 | Push 3 | [5, 3] |
+ | Pop 3 and 5, compute 5 + 3 = 8, push 8 | [8] |
8 | Push 8 | [8, 8] |
2 | Push 2 | [8, 8, 2] |
- | Pop 2 and 8, compute 8 - 2 = 6, push 6 | [8, 6] |
* | Pop 6 and 8, compute 8 * 6 = 48, push 48 | [48] |
Final result: 48
The order matters when you pop. For subtraction and division, the second-popped value is the left operand. So if the stack has [8, 2] and you see -, you compute 8 - 2, not 2 - 8.
This uses the shunting-yard approach (a stack for operators, direct output for operands):
Read the expression left to right.
If the token is an operand, output it immediately.
If the token is an operator, pop and output any operators on the stack that have equal or higher precedence, then push the current operator.
At the end, pop and output all remaining operators.
Worked example: A + B * C
Token | Action | Stack | Output so far |
|---|---|---|---|
A | Output A | [] | A |
+ | Push + | [+] | A |
B | Output B | [+] | A B |
* | Push * (higher precedence than +, so + stays) | [+, *] | A B |
C | Output C | [+, *] | A B C |
end | Pop * then + | [] | A B C * + |
Postfix result: A B C * +
The key rule: has higher precedence than +, so when arrives and + is on the stack, + is not popped (because + has lower precedence). When + arrives and is on the stack, would be popped first (because * has equal or higher precedence).
Both postfix evaluation and infix-to-postfix conversion need temporary storage with a "most recent first" retrieval pattern. In postfix evaluation, the most recent operands are the ones the next operator needs. In infix-to-postfix, operators with higher precedence need to come out before lower-precedence ones that arrived earlier. LIFO ordering handles both naturally.
The most commonly examined bug is the pointer-type mistake in a linked list push function.
Buggy code:
void push(struct Node* top, int val) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = top;
top = newNode; // Only modifies the local copy
}
The fix: change the parameter to struct Node** top and dereference throughout:
void push(struct Node** top, int val) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = *top;
*top = newNode; // Modifies the caller's pointer
}
Why it matters: C passes arguments by value. A struct Node* parameter is a copy of the pointer. Assigning to it inside the function has no effect on the original. A struct Node** parameter is a pointer to the pointer, so dereferencing it (*top) reaches the original.
Operator precedence table (standard for this course)
Precedence level | Operators |
|---|---|
Higher |
|
Lower |
|
When converting infix to postfix, an incoming operator pops stack operators of equal or higher precedence before being pushed.
Postfix notation is the basis for stack-based calculators (HP calculators, Forth programming language) and is how compilers internally represent arithmetic after parsing. Infix-to-postfix conversion is a simplified version of what a compiler's parser does when it encounters mathematical expressions in your source code. DFS is used in maze solving, topological sorting, cycle detection in graphs, and solving puzzles like Sudoku via backtracking.
When evaluating postfix, students often get the operand order wrong for subtraction and division. The second value popped is the left operand. 8 2 - means 8 - 2, not 2 - 8. Write out "second popped OP first popped" to keep it straight.
In infix-to-postfix conversion, students sometimes pop all operators when a new one arrives, regardless of precedence. You only pop operators with equal or higher precedence than the incoming one.
Students often conflate BFS (breadth-first search) and DFS (depth-first search). DFS uses a stack. BFS uses a queue. If an exam asks "which algorithm commonly uses stacks," the answer is DFS, not BFS.
The bug-tracing question about the single pointer vs double pointer trips up students who do not trace through what C does with the argument. Draw the pointer diagram: the function gets its own copy of the pointer variable.
⚠️ Postfix evaluation tracing is a very common exam question. You are given an expression and asked to show the stack state after each token. Practice until you can do it without second-guessing operand order.
⚠️ Infix-to-postfix conversion is equally likely to appear. The key decision point is whether to pop the stack before pushing an operator. Memorise: pop if the stack top has equal or higher precedence.
⚠️ "Which application commonly uses stacks?" appears as an MCQ. The answer is depth-first search (B). Breadth-first search (A) uses a queue.
⚠️ The pointer-type bug (single vs double pointer in linked list push) is a standard bug-tracing question. Be ready to identify the problem and write the corrected function signature.
True or false: In postfix evaluation, when you encounter an operator, the first value popped is the left operand. False. The first popped is the right operand; the second popped is the left operand.
Fill in the blank: The postfix form of A + B C is ____. A B C +
True or false: Depth-first search uses a queue. False. DFS uses a stack. BFS uses a queue.
Fill in the blank: The result of evaluating the postfix expression 5 3 + 8 2 - * is ____. 48
True or false: In the buggy linked list push function that takes struct Node* top, the code compiles but the caller's pointer is never updated. True.
Q: Trace the stack during evaluation of the postfix expression 5 3 + 8 2 - * and give the final result.
A: Push 5, push 3. Pop 3 and 5, compute 5 + 3 = 8, push 8. Push 8, push 2. Pop 2 and 8, compute 8 - 2 = 6, push 6. Pop 6 and 8, compute 8 * 6 = 48, push 48. Final result: 48.
Q: Convert the infix expression A + B * C to postfix. Show the stack at each step.
A: Read A, output A. Read +, push +. Read B, output B. Read , push (higher precedence than +, so + stays). Read C, output C. End: pop , output ; pop +, output +. Postfix: A B C * +.
Q: Which of the following applications commonly uses stacks: breadth-first search, depth-first search, binary search, or merge sort?
A: Depth-first search. BFS uses a queue. Binary search and merge sort do not inherently use a stack as their primary data structure (though recursion uses the call stack implicitly).
Q: Why is a stack useful in recursion?
A: It stores function call frames, allowing the program to return to previous states when each recursive call completes. Each call's local variables and return address are preserved on the call stack.
Q: Fix the bug in this push function: void push(struct Node* top, int val).
A: Change the parameter to struct Node** top. Inside the function, replace top with top when reading or writing the pointer: newNode->next = top; and *top = newNode;.
Q: What is the postfix result of the infix expression (A + B) * C (with parentheses)?
A: A B + C . The parentheses force + to be evaluated before , so + is popped when the closing parenthesis is encountered, before * operates on the result.
Postfix evaluation connects to how interpreters and virtual machines (like the Java Virtual Machine) execute bytecode using an operand stack. Infix-to-postfix conversion is a simplified case of the shunting-yard algorithm, which also handles parentheses and function calls, and is a stepping stone to understanding recursive descent parsers. DFS connects to graph theory topics later in the course, including topological sorting and connected components, both of which rely on stack-based traversal.
postfix evaluation, reverse Polish notation, RPN, infix to postfix conversion, shunting-yard algorithm, operator precedence, stack tracing, output tracing, DFS, depth-first search, BFS vs DFS, stack applications, call stack, recursion stack, bug tracing stack, pointer to pointer bug, double pointer C, expression parsing, COP 3502, Computer Science I, UCF, stack exam questions, stack practice problems