Stack applications (expression evaluation, backtracking) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to push an element onto the stack.

Data Structures Theory

stack.[1](element)

Drag options to blanks, or click blank then click option'

Aremove

Bpop

Cpeek

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' instead of 'push' to add elements.

To add an element to the top of a stack, you use the push operation.

2fill in blank

medium

Complete the code to check if the stack is empty before popping.

Data Structures Theory

if not stack.[1]():
    stack.pop()

Drag options to blanks, or click blank then click option'

Ais_empty

Bpush

Cpeek

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'peek' or 'size' which do not return a boolean for emptiness.

Before removing an element, you check if the stack is empty using is_empty() to avoid errors.

3fill in blank

hard

Fix the error in the expression evaluation code by completing the blank.

Data Structures Theory

while stack and precedence(stack[-1]) >= precedence([1]):
    output.append(stack.pop())

Drag options to blanks, or click blank then click option'

Acurrent_op

Bstack[-1]

Coutput[-1]

Dexpression[-1]

Attempts:

3 left

💡 Hint

Common Mistakes

Using the top of the stack instead of the current operator.

We compare the precedence of the operator on top of the stack with the current operator being processed, here named current_op.

4fill in blank

hard

Fill both blanks to correctly implement backtracking with a stack.

Data Structures Theory

stack.[1](state)
while stack:
    current = stack.[2]()

Drag options to blanks, or click blank then click option'

Apush

Bpop

Cpeek

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'peek' or 'remove' which do not add or remove elements properly.

In backtracking, you push new states onto the stack and pop them to explore.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps operators to their precedence if precedence is greater than 1.

Data Structures Theory

precedence_map = { [1]: [2] for [1], [2] in [3].items() if [2] > 1 }

Drag options to blanks, or click blank then click option'

Aop

Bprec

Coperators

Ditems

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'items' as a variable name or repeating the same variable for key and value.

This comprehension iterates over operators dictionary items, unpacking keys as op and values as prec, then filters by precedence > 1.

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