Evaluate Postfix Expression Using Stack in DSA Rust

Mental Model

We use a stack to keep numbers until we find an operator, then combine the last two numbers using that operator.

Analogy: Imagine a chef stacking ingredients on a plate. When the chef sees a cooking instruction, they take the last two ingredients, mix them, and put the result back on the plate.

Stack (top at right): []
Expression: 2 3 + 4 *

Initial stack is empty.
Numbers push onto stack -> [2] -> [2,3]
Operator '+' pops last two numbers, adds, pushes result -> [5]
Next number 4 pushes -> [5,4]
Operator '*' pops last two, multiplies, pushes -> [20]

Dry Run Walkthrough

Input: postfix expression: 2 3 + 4 *

Goal: Calculate the final value of the postfix expression using a stack

Step 1: Read '2', push onto stack

Stack: [2]

Why: Numbers go on stack to wait for operators

Step 2: Read '3', push onto stack

Stack: [2, 3]

Why: Keep numbers until operator appears

Step 3: Read '+', pop 3 and 2, add to get 5, push 5

Stack: [5]

Why: Operator applies to last two numbers on stack

Step 4: Read '4', push onto stack

Stack: [5, 4]

Why: Push next number to stack

Step 5: Read '*', pop 4 and 5, multiply to get 20, push 20

Stack: [20]

Why: Apply operator to last two numbers

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA Rust

use std::io;

fn evaluate_postfix(expression: &str) -> i32 {
    let mut stack: Vec<i32> = Vec::new();
    for token in expression.split_whitespace() {
        if let Ok(num) = token.parse::<i32>() {
            stack.push(num); // push number to stack
        } else {
            let right = stack.pop().expect("Stack underflow"); // pop right operand
            let left = stack.pop().expect("Stack underflow"); // pop left operand
            let result = match token {
                "+" => left + right, // add
                "-" => left - right, // subtract
                "*" => left * right, // multiply
                "/" => left / right, // divide
                _ => panic!("Unknown operator"),
            };
            stack.push(result); // push result back
        }
    }
    stack.pop().expect("No result on stack")
}

fn main() {
    let expression = "2 3 + 4 *";
    let result = evaluate_postfix(expression);
    println!("{}", result);
}

stack.push(num); // push number to stack

push numbers onto stack to wait for operators

let right = stack.pop().expect("Stack underflow"); // pop right operand

pop last number as right operand for operation

let left = stack.pop().expect("Stack underflow"); // pop left operand

pop second last number as left operand

let result = match token { ... }

apply operator to left and right operands

stack.push(result); // push result back

push operation result back to stack

Output

20

Complexity Analysis

Time: O(n) because we process each token in the expression once

Space: O(n) because in worst case all tokens are numbers pushed onto the stack

vs Alternative: Compared to evaluating infix expressions which require operator precedence handling, postfix evaluation is simpler and faster with a stack

Edge Cases

Empty expression

Function panics or returns error due to no result on stack

DSA Rust

stack.pop().expect("No result on stack")

Expression with single number

Returns that number as result

DSA Rust

stack.pop().expect("No result on stack")

Invalid operator

Panics with 'Unknown operator' message

DSA Rust

panic!("Unknown operator")

When to Use This Pattern

When you see expressions without parentheses and operators after operands, use stack evaluation of postfix expressions to simplify calculation.

Common Mistakes

Mistake: Popping operands in wrong order causing incorrect results
Fix: Always pop right operand first, then left operand to maintain correct order

Summary

Evaluates a postfix expression by using a stack to store operands and applying operators to the last two operands.

Use when you need to calculate expressions written in postfix notation without worrying about operator precedence.

The key insight is that operators always apply to the last two numbers pushed on the stack.

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