Evaluate Postfix Expression Using Stack in DSA C++ - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Start

↓

Read next token

↓

Is token operand?

Yes→Push operand on stack

↓

Stack grows

↓

Is token operator?

Yes→Pop two operands from stack

↓

Apply operator

↓

Error or End?

No→Push result back on stack

↓

Stack updated

↓

End of expression?

No→Repeat reading tokens

Yes↓

Pop final result from stack

↓

Done

The flow reads each token from the postfix expression. If it's a number, push it on the stack. If it's an operator, pop two numbers, apply the operator, and push the result back. Repeat until expression ends, then pop the final result.

Execution Sample

DSA C++

string expr = "231*+9-";
stack<int> s;
for (char c : expr) {
  if (isdigit(c)) s.push(c - '0');
  else {
    int b = s.top(); s.pop();
    int a = s.top(); s.pop();
    s.push(applyOp(a, b, c));
  }
}
int result = s.top();

Evaluates postfix expression "231*+9-" step-by-step using a stack.

Execution Table

Step	Operation	Token	Stack Before	Action	Stack After	Visual State
1	Read token	2	[]	Push 2	[2]	2 -> null
2	Read token	3	[2]	Push 3	[2, 3]	2 -> 3 -> null
3	Read token	1	[2, 3]	Push 1	[2, 3, 1]	2 -> 3 -> 1 -> null
4	Read token	*	[2, 3, 1]	Pop 1 and 3, multiply 3*1=3, push 3	[2, 3]	2 -> 3 -> null
5	Read token	+	[2, 3]	Pop 3 and 2, add 2+3=5, push 5	[5]	5 -> null
6	Read token	9	[5]	Push 9	[5, 9]	5 -> 9 -> null
7	Read token	-	[5, 9]	Pop 9 and 5, subtract 5-9=-4, push -4	[-4]	-4 -> null
8	End of expression		[-4]	Pop final result	[]	empty

💡 All tokens processed; final result popped from stack.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
Stack	[]	[2]	[2,3]	[2,3,1]	[2,3]	[5]	[5,9]	[-4]	[]
Top Element	N/A	2	3	1	3	5	9	-4	N/A

Key Moments - 3 Insights

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

Because postfix operators apply to the two most recent operands on the stack, as shown in steps 4, 5, and 7 where two values are popped before applying the operator.

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

Because the result might be used in further operations, so it must be available on the stack, as seen in steps 4, 5, and 7 where the computed value is pushed back.

What happens if the expression ends but the stack has more than one value?

This indicates an invalid postfix expression. In this example, the stack has only one value at the end (step 8), which is the correct final result.

Visual Quiz - 3 Questions

Look at the execution table, what is the stack after step 5?

A [2, 3]

B [2, 3, 1]

C [5]

D [5, 9]

💡 Hint

Check the 'Stack After' column for step 5 in the execution table.

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

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the '*' token in the 'Token' column and see the corresponding step.

If the token '9' was missing, what would be the stack after step 6?

A [5]

B [5, 9]

C [2, 3]

D [-4]

💡 Hint

Without pushing '9' at step 6, the stack remains as after step 5.

Concept Snapshot

Evaluate Postfix Expression Using Stack:
- Read tokens left to right
- Push numbers on stack
- On operator, pop two numbers, apply operator, push result
- Repeat until end
- Final stack top is result

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 top two numbers from the stack, apply the operator, and push the result back onto the stack. We repeat this process until all tokens are processed. At the end, the stack contains the final result, which we pop and return. This method uses a stack to keep track of operands and intermediate results, ensuring correct order of operations without parentheses.

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 process

   Postfix expressions are evaluated by scanning from left to right and using a stack to store operands.

2. Step 2: Identify the data structure used

   Operands are pushed onto the stack, and when an operator is found, operands are popped for calculation, then the result is pushed back.

3. Final Answer:

   Stack -> Option B

4. Quick Check:

   Postfix evaluation uses Stack [OK]

Hint: Remember: postfix needs LIFO structure, so use stack [OK]

Common Mistakes:

• Using queue instead of stack
• Trying to evaluate without any data structure
• Confusing postfix with infix evaluation

2. Which of the following is the correct syntax to push an integer value '5' onto a stack named 's' in C++?

easy

A. push(s, 5);

B. s.insert(5);

C. s.add(5);

D. s.push(5);

Solution

1. Step 1: Recall C++ stack push syntax

   The standard C++ stack uses the member function push() to add elements.

2. Step 2: Match syntax with options

   Only s.push(5); uses s.push(5); which is correct syntax.

3. Final Answer:

   s.push(5); -> Option D

4. Quick Check:

   Stack push syntax = s.push(value) [OK]

Hint: Use s.push(value) to add elements to stack [OK]

Common Mistakes:

• Using non-existent methods like add() or insert()
• Calling push as a free function instead of member function
• Confusing push with pop

3. What is the output of the following C++ code that evaluates the postfix expression "231*+9-"?

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int evaluatePostfix(string exp) {
    stack<int> s;
    for (char c : exp) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int val2 = s.top(); s.pop();
            int val1 = s.top(); s.pop();
            switch(c) {
                case '+': s.push(val1 + val2); break;
                case '-': s.push(val1 - val2); break;
                case '*': s.push(val1 * val2); break;
                case '/': s.push(val1 / val2); break;
            }
        }
    }
    return s.top();
}

int main() {
    cout << evaluatePostfix("231*+9-");
    return 0;
}

medium

A. -4

B. -2

C. 4

D. 2

Solution

1. Step 1: Evaluate postfix expression "231*+9-" step-by-step

   Push 2, push 3, push 1. '*' operator: pop 1 and 3, multiply 3*1=3, push 3. '+' operator: pop 3 and 2, add 2+3=5, push 5. Push 9. '-' operator: pop 9 and 5, subtract 5-9=-4, push -4.

2. Step 2: Final value on stack is -4

   After all operations, the stack top is -4, which is the result printed.

3. Final Answer:

   -4 -> Option A

4. Quick Check:

   Postfix "231*+9-" = -4 [OK]

Hint: Evaluate stepwise: push numbers, apply operators on top two [OK]

Common Mistakes:

• Mixing operand order in subtraction
• Forgetting to convert char digits to int
• Popping operands in wrong order

4. The following code snippet is intended to evaluate a postfix expression but produces incorrect results. What is the bug?

int evaluatePostfix(string exp) {
    stack<int> s;
    for (char c : exp) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int val1 = s.top(); s.pop();
            int val2 = s.top(); s.pop();
            switch(c) {
                case '+': s.push(val1 + val2); break;
                case '-': s.push(val1 - val2); break;
                case '*': s.push(val1 * val2); break;
                case '/': s.push(val1 / val2); break;
            }
        }
    }
    return s.top();
}

medium

A. Missing return statement

B. isdigit() check is incorrect

C. Operands val1 and val2 are popped in wrong order

D. Stack is not initialized properly

Solution

1. Step 1: Analyze operand popping order

   The code pops val1 first, then val2. In postfix evaluation, val2 is the top operand, val1 is below it.

2. Step 2: Correct operand order for operations

   Operations should be val1 (second popped) operator val2 (first popped). The code reverses this, causing wrong results.

3. Final Answer:

   Operands val1 and val2 are popped in wrong order -> Option C

4. Quick Check:

   Operand order matters: val2 = top, val1 = next [OK]

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

Common Mistakes:

• Swapping operand order in operations
• Not popping operands before using them
• Confusing isdigit() usage

5. Given the postfix expression "56+82/-", what is the final result after evaluation using a stack?

hard

A. 7

B. 5

C. 1

D. 3

Solution

1. Step 1: Evaluate postfix "56+82/-" stepwise

   Push 5, push 6. '+' operator: pop 6 and 5, add 5+6=11, push 11. Push 8, push 2. '/' operator: pop 2 and 8, divide 8/2=4, push 4. '-' operator: pop 4 and 11, subtract 11-4=7, push 7.

2. Step 2: Final value on stack is 7

   After all operations, the stack top is 7, which is the result.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Postfix "56+82/-" = 7 [OK]

Hint: Process operators immediately on top two stack values [OK]

Common Mistakes:

• Incorrect operand order in division and subtraction
• Misreading the expression characters
• Forgetting to convert char digits to int