Stack applications (expression evaluation, backtracking) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Expression Evaluation Using Stacks

Consider the infix expression: (3 + 4) * 5 - 6. When evaluating this expression using two stacks (one for operators and one for operands), what is the value on the operand stack just before the final subtraction operation is applied?

A 35

B 29

C 20

D 7

💡 Hint

Evaluate the expression step-by-step, applying operator precedence and parentheses.

The expression evaluates as follows: (3 + 4) = 7, then 7 * 5 = 35, finally 35 - 6 = 29. Just before the subtraction, the operand stack holds 35.

❓ Reasoning

intermediate

Backtracking with Stacks in Maze Solving

In a maze-solving algorithm using backtracking with a stack, what does pushing a position onto the stack represent?

A Storing the shortest path found so far

B Deleting a path that leads to a dead end

C Marking a position as visited and exploring it later

D Recording a path choice to return to if a dead end is reached

💡 Hint

Think about how backtracking remembers where to return after exploring a path.

Pushing a position onto the stack records a choice point. If the path leads to a dead end, the algorithm can pop the stack to backtrack to that position and try another path.

🔍 Analysis

advanced

Output of Postfix Expression Evaluation

What is the result of evaluating the postfix expression 6 2 3 + - 3 8 2 / + * using a stack?

A 30

B 36

C 7

D 24

💡 Hint

Process the postfix expression from left to right, pushing numbers and applying operators.

Step-by-step evaluation:
Push 6 → [6]
Push 2 → [6, 2]
Push 3 → [6, 2, 3]
+ : pop 3, 2; 2 + 3 = 5; push 5 → [6, 5]
- : pop 5, 6; 6 - 5 = 1; push 1 → [1]
Push 3 → [1, 3]
Push 8 → [1, 3, 8]
Push 2 → [1, 3, 8, 2]
/ : pop 2, 8; 8 / 2 = 4; push 4 → [1, 3, 4]
+ : pop 4, 3; 3 + 4 = 7; push 7 → [1, 7]
* : pop 7, 1; 1 * 7 = 7; push 7 → [7]
Final result: 7

❓ Comparison

advanced

Comparing Stack and Recursion in Backtracking

Which statement best describes the relationship between using an explicit stack and recursion for backtracking algorithms?

A Recursion uses the call stack implicitly, while an explicit stack replaces this with manual control

B Recursion is always more memory efficient than using an explicit stack

C Recursion and explicit stacks are unrelated concepts in backtracking

D An explicit stack cannot handle backtracking as effectively as recursion

💡 Hint

Think about how function calls are managed in recursion versus manual stack usage.

Recursion uses the system's call stack to remember states, while using an explicit stack means managing these states manually. Both achieve backtracking but differ in control and sometimes efficiency.

📋 Factual

expert

Error Identification in Expression Evaluation Algorithm

In an algorithm that evaluates arithmetic expressions using stacks, which of the following errors will occur if the operator stack is popped without checking if it is empty?

A SyntaxError because the expression is malformed

B StackUnderflowError or equivalent runtime error due to popping from an empty stack

C Logical error but no runtime error occurs

D No error; the algorithm handles empty stacks automatically

💡 Hint

Consider what happens when you try to remove an item from an empty container.

Popping from an empty stack causes a runtime error such as StackUnderflowError or IndexError, depending on the implementation. This must be checked to avoid crashes.

Practice

1. What is the main purpose of a stack in data structures?

easy

A. To store data randomly

B. To store data in first-in, first-out order

C. To store data in last-in, first-out order

D. To store data permanently

Solution

1. Step 1: Understand stack behavior

   A stack stores data so the last item added is the first one removed, called last-in, first-out (LIFO).

2. Step 2: Compare options with stack definition

   To store data in last-in, first-out order matches the LIFO behavior, while others describe different data structures or incorrect behavior.

3. Final Answer:

   To store data in last-in, first-out order -> Option C

4. Quick Check:

   Stack = LIFO order [OK]

Hint: Remember stack = last item in, first item out [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking stack stores data randomly
• Assuming stack stores data permanently

2. Which of the following is the correct way to push an element x onto a stack named s?

easy

A. s.push(x)

B. s.pop(x)

C. s.enqueue(x)

D. s.insert(x)

Solution

1. Step 1: Identify stack operations

   Common stack operations are push (add), pop (remove), peek (view top).

2. Step 2: Match operation to pushing element

   To add element x, use push. Pop removes element. Enqueue is for queues. Insert is not standard stack method.

3. Final Answer:

   s.push(x) -> Option A

4. Quick Check:

   Push means add element [OK]

Hint: Push adds, pop removes from stack top [OK]

Common Mistakes:

• Using pop to add elements
• Confusing queue methods with stack
• Using non-standard method names

3. Consider the expression (3 + 2) * (4 - 1). Using a stack to evaluate this expression step-by-step, what is the final result?

medium

A. 15

B. 9

C. 21

D. Error

Solution

1. Step 1: Evaluate inside parentheses first

   (3 + 2) = 5 and (4 - 1) = 3

2. Step 2: Multiply the results

   5 * 3 = 15

3. Final Answer:

   15 -> Option A

4. Quick Check:

   (3+2)*(4-1) = 15 [OK]

Hint: Calculate parentheses first, then multiply [OK]

Common Mistakes:

• Ignoring parentheses order
• Adding instead of multiplying
• Confusing subtraction sign

4. A program uses a stack to check if brackets in an expression are balanced. Which of the following errors would cause the program to incorrectly say brackets are balanced?

medium

A. Pushing opening brackets onto the stack

B. Not popping from stack when a closing bracket is found

C. Ignoring characters other than brackets

D. Checking stack is empty at the end

Solution

1. Step 1: Understand bracket checking with stack

   Opening brackets are pushed; closing brackets pop the matching opening bracket.

2. Step 2: Identify error impact

   If popping is skipped on closing bracket, stack keeps extra openings, so program misses imbalance.

3. Final Answer:

   Not popping from stack when a closing bracket is found -> Option B

4. Quick Check:

   Pop on closing bracket needed [OK]

Hint: Pop stack on closing bracket to check balance [OK]

Common Mistakes:

• Forgetting to pop on closing bracket
• Pushing closing brackets instead of opening
• Not checking stack emptiness at end

5. In backtracking algorithms, how does a stack help in exploring possible solutions?

hard

A. By preventing any repeated steps automatically

B. By storing all solutions at once for quick access

C. By sorting the solutions in ascending order

D. By remembering choices and allowing undoing steps when a path fails

Solution

1. Step 1: Understand backtracking process

   Backtracking tries choices step-by-step and undoes them if they lead to failure.

2. Step 2: Role of stack in backtracking

   Stack stores the choices made so far, allowing the algorithm to go back (undo) when needed.

3. Final Answer:

   By remembering choices and allowing undoing steps when a path fails -> Option D

4. Quick Check:

   Stack = remember and undo choices [OK]

Hint: Stack tracks choices to backtrack easily [OK]

Common Mistakes:

• Thinking stack stores all solutions simultaneously
• Assuming stack sorts solutions
• Believing stack prevents repeated steps automatically