Stack applications (expression evaluation, backtracking) in Data Structures Theory - Mini Project: Build & Apply

Stack Applications: Expression Evaluation and Backtracking

📖 Scenario: Imagine you are building a simple calculator that can evaluate arithmetic expressions and also a tool that helps solve puzzles by trying different options and going back when stuck.

🎯 Goal: You will create a step-by-step guide to understand how stacks help in evaluating expressions and in backtracking to find solutions.

📋 What You'll Learn

Create a list of tokens representing an arithmetic expression

Set up a stack to hold numbers during evaluation

Use a loop to process each token and apply stack operations

Add a mechanism to backtrack choices using a stack

💡 Why This Matters

🌍 Real World

Stacks are used in calculators to evaluate expressions and in puzzle games or algorithms to try options and backtrack when needed.

💼 Career

Understanding stacks and their applications is important for software developers working on compilers, interpreters, game development, and algorithm design.

1

Create the expression tokens list

Create a list called expression_tokens with these exact string elements in order: '3', '4', '+', '2', '*', '7'.

Data Structures Theory

# Create the list expression_tokens with the exact tokens
# Your code here

Hint

Think of the expression as a list of numbers and operators in the order they appear.

2

Set up an empty stack for evaluation

Create an empty list called stack to use as a stack for holding numbers during expression evaluation.

Data Structures Theory

expression_tokens = ['3', '4', '+', '2', '*', '7']
# Create an empty list called stack
# Your code here

Hint

A stack can be represented by an empty list where you add and remove items from the end.

3

Evaluate the expression using the stack

Write a for loop using token to go through each item in expression_tokens. Inside the loop, if token is a digit, convert it to an integer and append it to stack. If token is an operator '+' or '*', pop the last two numbers from stack, apply the operator, and append the result back to stack.

Data Structures Theory

expression_tokens = ['3', '4', '+', '2', '*', '7']
stack = []
# Loop through expression_tokens and evaluate using stack
# Your code here

Hint

Use isdigit() to check if the token is a number. Use pop() to get the last two numbers and then add or multiply them.

4

Add backtracking stack for choices

Create an empty list called backtrack_stack to store choices during backtracking. Then append the string 'start' to backtrack_stack to mark the beginning of choices.

Data Structures Theory

expression_tokens = ['3', '4', '+', '2', '*', '7']
stack = []
for token in expression_tokens:
    if token.isdigit():
        stack.append(int(token))
    elif token == '+':
        b = stack.pop()
        a = stack.pop()
        stack.append(a + b)
    elif token == '*':
        b = stack.pop()
        a = stack.pop()
        stack.append(a * b)
# Create backtrack_stack and add 'start'
# Your code here

Hint

Backtracking uses a stack to remember where to return. Start by creating an empty list and add a marker.

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