Evaluate Postfix Expression Using Stack in DSA C++

Mental Model

Use a stack to keep numbers until an operator comes, then combine the last two numbers and push the result back.

Analogy: Imagine a chef stacking ingredients on a plate. When the chef gets a cooking instruction (operator), they take the last two ingredients, cook them together, and put the cooked dish back on the plate.

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

Initial stack empty -> []
Numbers push on stack -> [2] -> [2,3]
Operator '+' pops last two, adds, pushes result -> [5]
Next number pushes -> [5,4]
Operator '*' pops last two, multiplies, pushes result -> [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 it onto the stack

Stack: [2]

Why: Numbers are pushed to stack to wait for operators

Step 2: Read '3', push it onto the stack

Stack: [2, 3]

Why: Keep numbers on stack until operator appears

Step 3: Read '+', pop top two numbers (3 and 2), add them (2+3=5), push result back

Stack: [5]

Why: Operator applies to last two numbers, result replaces them

Step 4: Read '4', push it onto the stack

Stack: [5, 4]

Why: Push next number to stack

Step 5: Read '*', pop top two numbers (4 and 5), multiply them (5*4=20), push result back

Stack: [20]

Why: Operator applies to last two numbers, result replaces them

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA C++

#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

int evaluatePostfix(const string& expr) {
    stack<int> s;
    for (char ch : expr) {
        if (isspace(ch)) continue; // skip spaces
        if (isdigit(ch)) {
            s.push(ch - '0'); // push number
        } else {
            int val2 = s.top(); s.pop(); // pop second operand
            int val1 = s.top(); s.pop(); // pop first operand
            int res = 0;
            if (ch == '+') res = val1 + val2;
            else if (ch == '-') res = val1 - val2;
            else if (ch == '*') res = val1 * val2;
            else if (ch == '/') res = val1 / val2;
            s.push(res); // push result
        }
    }
    return s.top();
}

int main() {
    string expr = "2 3 + 4 *";
    int result = evaluatePostfix(expr);
    cout << result << endl;
    return 0;
}

if (isdigit(ch)) { s.push(ch - '0'); }

push number characters as integers onto stack

int val2 = s.top(); s.pop(); int val1 = s.top(); s.pop();

pop last two numbers for operation

if (ch == '+') res = val1 + val2; else if (ch == '-') res = val1 - val2; else if (ch == '*') res = val1 * val2; else if (ch == '/') res = val1 / val2;

apply operator to popped numbers

s.push(res);

push operation result back onto stack

Output

20

Complexity Analysis

Time: O(n) because we scan the expression once, processing each character

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

vs Alternative: Compared to evaluating infix expressions with parentheses and precedence, postfix evaluation is simpler and faster because it uses a stack without needing to handle precedence rules

Edge Cases

Empty expression

Returns top of empty stack would cause error; code skips processing and returns nothing

DSA C++

No explicit guard; input should be validated before calling

Expression with single number only

Returns that number as result

DSA C++

if (isdigit(ch)) { s.push(ch - '0'); }

Division by zero

Code does not handle division by zero explicitly; may cause runtime error

DSA C++

No explicit guard in code

When to Use This Pattern

When you see an expression with operators after operands and need to compute its value, use the Evaluate Postfix Expression pattern with a stack to handle operations in order without parentheses.

Common Mistakes

Mistake: Popping operands in wrong order causing incorrect results
Fix: Always pop second operand first, then first operand, because stack is LIFO

Mistake: Not skipping spaces causing errors
Fix: Add check to skip whitespace characters before processing

Summary

It calculates the value of a postfix expression using a stack.

Use it when you have postfix expressions and want to evaluate them efficiently.

The key insight is to push numbers and apply operators to the last two numbers 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 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