Evaluate Postfix Expression Using Stack in DSA Rust - Time & Space Complexity

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to evaluate a postfix expression changes as the expression gets longer.

Specifically, how the number of steps grows with the number of symbols in the expression.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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()
}
    

This code reads each symbol in the postfix expression once, using a stack to compute the result step-by-step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the expression once.
• How many times: Exactly once per symbol in the expression.

How Execution Grows With Input

Each symbol causes a fixed number of steps: either pushing a number or popping two numbers and pushing one result.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The number of steps grows directly with the number of symbols; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows in a straight line with the length of the expression.

Common Mistake

[X] Wrong: "Evaluating postfix expressions takes more than linear time because of nested operations."

[OK] Correct: Each symbol is processed once, and stack operations are fast, so the total work is proportional to the number of symbols, not more.

Interview Connect

Understanding this linear time evaluation shows you can handle stack-based algorithms efficiently, a common skill in coding challenges and interviews.

Self-Check

"What if the expression included multi-digit numbers separated by spaces? How would the time complexity change?"

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