Evaluate Postfix Expression Using Stack in DSA Rust - Build from Scratch

Evaluate Postfix Expression Using Stack

📖 Scenario: You are building a simple calculator that reads a postfix expression and calculates the result. Postfix expressions have operators after their operands, like 23+ which means 2 + 3.This calculator uses a stack to keep track of numbers and applies operators step-by-step.

🎯 Goal: Build a Rust program that uses a stack to evaluate a postfix expression and prints the final result.

📋 What You'll Learn

Create a vector of characters representing the postfix expression

Create a stack using a vector to hold integer values

Loop through each character in the postfix expression

Push numbers onto the stack

Pop two numbers from the stack when an operator is found and apply the operator

Push the result back onto the stack

Print the final result from the stack

💡 Why This Matters

🌍 Real World

Postfix expressions are used in calculators and compilers to evaluate mathematical expressions efficiently without parentheses.

💼 Career

Understanding stack-based expression evaluation is important for software developers working on interpreters, compilers, and calculators.

1

Create the postfix expression vector

Create a vector called postfix_expr with these exact characters: '2', '3', '1', '*', '+', '9', '-'

DSA Rust

# Create the postfix expression vector
# Your code here

Hint

Use vec![] to create a vector of characters.

2

Create an empty stack vector for integers

Add a mutable vector called stack of type Vec initialized as empty after the postfix_expr declaration

DSA Rust

fn main() {
    let postfix_expr = vec!['2', '3', '1', '*', '+', '9', '-'];
    // Create an empty stack vector for integers
    // Your code here
}

Hint

Use let mut stack: Vec = Vec::new(); to create an empty stack.

3

Loop through the postfix expression and evaluate

Add a for loop with variable ch iterating over postfix_expr. Inside the loop, if ch is a digit, convert it to i32 and push it to stack. If ch is an operator '+', '-', or '*', pop two values from stack, apply the operator, and push the result back to stack. Use stack.pop().unwrap() to pop values safely.

DSA Rust

fn main() {
    let postfix_expr = vec!['2', '3', '1', '*', '+', '9', '-'];
    let mut stack: Vec = Vec::new();

    // Loop through postfix_expr and evaluate
    // Your code here
}

Hint

Use ch.is_digit(10) to check if character is a digit. Use match to apply operators.

4

Print the final result from the stack

Add a println! statement to print the last value in stack using stack.pop().unwrap() after the loop ends

DSA Rust

fn main() {
    let postfix_expr = vec!['2', '3', '1', '*', '+', '9', '-'];
    let mut stack: Vec = Vec::new();

    for ch in postfix_expr {
        if ch.is_digit(10) {
            let num = ch.to_digit(10).unwrap() as i32;
            stack.push(num);
        } else {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            let res = match ch {
                '+' => a + b,
                '-' => a - b,
                '*' => a * b,
                _ => 0,
            };
            stack.push(res);
        }
    }

    // Print the final result
    // Your code here
}

Hint

The final result of the postfix expression is printed as an integer.

Practice

1. What is the main data structure used to evaluate a postfix expression?

easy

A. Queue

B. Stack

C. Array

D. Linked List

Solution

1. Step 1: Understand postfix evaluation method

   Postfix expressions are evaluated using a stack because operands are pushed and operators pop operands to compute results.

2. Step 2: Identify the correct data structure

   Stack allows last-in, first-out operations needed for postfix evaluation.

3. Final Answer:

   Stack -> Option B

4. Quick Check:

   Postfix evaluation uses stack [OK]

Hint: Postfix needs last-in, first-out structure: stack [OK]

Common Mistakes:

• Using queue instead of stack
• Trying to evaluate without any data structure
• Using array without stack logic

2. Which Rust code snippet correctly pushes an integer onto a stack represented by a vector named stack?

easy

A. stack.append(5);

B. stack.add(5);

C. stack.push(5);

D. stack.insert(5);

Solution

1. Step 1: Recall Rust vector push method

   Rust vectors use push to add elements at the end.

2. Step 2: Match correct method to push integer

   stack.push(5); correctly adds 5 to the vector stack.

3. Final Answer:

   stack.push(5); -> Option C

4. Quick Check:

   Use push() to add element to vector [OK]

Hint: Use push() to add elements to Rust vectors [OK]

Common Mistakes:

• Using add() which doesn't exist
• Using insert() without index
• Using append() incorrectly

3. What is the output of the following Rust code that evaluates the postfix expression "23+5*"?

fn evaluate_postfix(expr: &str) -> i32 {
    let mut stack = Vec::new();
    for ch in expr.chars() {
        if ch.is_digit(10) {
            stack.push(ch.to_digit(10).unwrap() as i32);
        } else {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            let res = match ch {
                '+' => a + b,
                '-' => a - b,
                '*' => a * b,
                '/' => a / b,
                _ => 0,
            };
            stack.push(res);
        }
    }
    stack.pop().unwrap()
}

fn main() {
    println!("{}", evaluate_postfix("23+5*"));
}

medium

A. 25

B. 15

C. 10

D. Error

Solution

1. Step 1: Evaluate postfix expression "23+5*" step-by-step

   Push 2, push 3, '+' pops 3 and 2, adds to 5, push 5, push 5, '*' pops 5 and 5, multiplies to 25.

2. Step 2: Final stack value after evaluation

   Stack ends with single value 25, which is printed.

3. Final Answer:

   25 -> Option A

4. Quick Check:

   2+3=5; 5*5=25 [OK]

Hint: Calculate stepwise: operands push, operators pop and compute [OK]

Common Mistakes:

• Mixing operand order
• Not popping two operands
• Confusing operator precedence

4. Identify the error in the following Rust code snippet that evaluates a postfix expression:

fn evaluate_postfix(expr: &str) -> i32 {
    let mut stack = Vec::new();
    for ch in expr.chars() {
        if ch.is_digit(10) {
            stack.push(ch.to_digit(10).unwrap() as i32);
        } else {
            let a = stack.pop().unwrap();
            let b = stack.pop().unwrap();
            let res = match ch {
                '+' => a + b,
                '-' => a - b,
                '*' => a * b,
                '/' => a / b,
                _ => 0,
            };
            stack.push(res);
        }
    }
    stack.pop().unwrap()
}

medium

A. Stack is not initialized

B. Using unwrap() causes panic

C. Missing handling for invalid characters

D. Operands are popped in wrong order (a and b swapped)

Solution

1. Step 1: Check operand popping order

   Operands must be popped as b then a to maintain correct order for operations like subtraction and division.

2. Step 2: Identify the swap error

   Code pops a first then b, which reverses operand order and causes wrong results.

3. Final Answer:

   Operands are popped in wrong order (a and b swapped) -> Option D

4. Quick Check:

   Pop b then a for correct operand order [OK]

Hint: Pop second operand first, then first operand [OK]

Common Mistakes:

• Swapping operand order
• Ignoring unwrap panic possibility
• Not validating input characters

5. Given the postfix expression "82/3-4*", what is the correct evaluation result using a stack-based approach in Rust?

hard

A. 4

B. 0

C. -4

D. 2

Solution

1. Step 1: Evaluate postfix "82/3-4*" stepwise

   Push 8, push 2, '/' pops 2 and 8, computes 8/2=4, push 4, push 3, '-' pops 3 and 4, computes 4-3=1, push 1, push 4, '*' pops 4 and 1, computes 1*4=4.

2. Step 2: Re-check calculation order and result

   Let's verify carefully: 8/2=4, then 3 popped, 4 popped, 4-3=1, then 4 pushed, 1 popped, 4 popped, 1*4=4.

3. Step 3: Check if operands popped in correct order

   Operands popped: b then a. For '-', a=4, b=3, so 4-3=1. For '*', a=1, b=4, so 1*4=4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   8/2=4; 4-3=1; 1*4=4 [OK]

Hint: Pop operands in correct order: second popped is first operand [OK]

Common Mistakes:

• Swapping operands in subtraction/division
• Misreading expression order
• Forgetting operator precedence is implicit in postfix