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

Need a 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

Need a 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

Need a 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

Need a hint?

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