Evaluate Postfix Expression Using Stack in DSA Rust - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Start

↓

Read next token

↓

Is token operand?

Yes→Push operand on stack

↓

Stack updated

↓

Pop two operands from stack

↓

Apply operator

↓

Push result back on stack

↓

More tokens?

Yes→Read next token

No↓

Pop final result from stack

↓

End

The process reads each token from the postfix expression. If it is a number, push it on the stack. If it is an operator, pop two numbers, apply the operator, and push the result back. Repeat until all tokens are processed, then pop the final result.

Execution Sample

DSA Rust

let expr = "23+5*";
let mut stack = Vec::new();
for token in expr.chars() {
    if token.is_digit(10) {
        stack.push(token.to_digit(10).unwrap());
    } else {
        let b = stack.pop().unwrap();
        let a = stack.pop().unwrap();
        let res = apply_op(a, b, token);
        stack.push(res);
    }
}
let result = stack.pop().unwrap();

This code evaluates the postfix expression "23+5*" step-by-step using a stack.

Execution Table

Step	Operation	Token	Stack Before	Stack After	Visual State
1	Read token	2	[]	[2]	[2]
2	Read token	3	[2]	[2, 3]	[2, 3]
3	Operator '+' found	+	[2, 3]	[5]	[5] (2 + 3)
4	Read token	5	[5]	[5, 5]	[5, 5]
5	Operator '*' found	*	[5, 5]	[25]	[25] (5 * 5)
6	End of expression	N/A	[25]	[]	Final result: 25

💡 All tokens processed; final result popped from stack.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
stack	[]	[2]	[2, 3]	[5]	[5, 5]	[25]	[]
token	N/A	'2'	'3'	'+'	'5'	'*'	N/A
a (popped)	N/A	N/A	N/A	2	N/A	5	N/A
b (popped)	N/A	N/A	N/A	3	N/A	5	N/A
result (pushed)	N/A	N/A	N/A	5	N/A	25	N/A

Key Moments - 3 Insights

Why do we pop two operands when we find an operator?

Because postfix notation places operators after their operands, so to apply the operator, we need the last two numbers pushed on the stack. See step 3 and 5 in the execution_table where two values are popped before applying '+' and '*'.

What happens if the expression has only one number and no operators?

The number is pushed onto the stack and at the end, popped as the final result. The stack never pops two operands because no operator is found. This is shown in the initial steps where operands are pushed.

Why do we push the result back on the stack after applying an operator?

Because the result might be used by the next operator. The stack keeps intermediate results. For example, after '+' at step 3, the result 5 is pushed back for the next '*' operation.

Visual Quiz - 3 Questions

Look at the execution_table, what is the stack after step 3?

A [5]

B [2, 3]

C [3]

D [2]

💡 Hint

Check the 'Stack After' column for step 3 in the execution_table.

At which step does the operator '*' get processed?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Operation' and 'Token' columns in the execution_table.

If the expression was "23+", what would be the final stack state before popping the result?

A [5]

B [2, 3]

C [6]

D []

💡 Hint

Refer to the pattern in the execution_table for '+' operator processing.

Concept Snapshot

Evaluate Postfix Expression Using Stack:
- Read tokens left to right
- Push numbers on stack
- On operator, pop two numbers
- Apply operator and push result
- Final stack pop is result
- Works because postfix places operators after operands

Full Transcript

To evaluate a postfix expression, we read each token from left to right. If the token is a number, we push it onto a stack. If the token is an operator, we pop the last two numbers from the stack, apply the operator, and push the result back. We repeat this until all tokens are processed. At the end, the stack contains the final result which we pop and return. For example, in the expression "23+5*", we push 2 and 3, then apply '+', pushing 5 back. Then push 5, apply '*', and push 25. The final result is 25.

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