Evaluate Postfix Expression Using Stack in DSA C++ - Build from Scratch

Evaluate Postfix Expression Using Stack

📖 Scenario: You are building a simple calculator that reads a postfix expression (also called Reverse Polish Notation) and calculates the result. Postfix expressions are used in calculators and computer programs to avoid confusion with parentheses.For example, the postfix expression 23+ means 2 + 3, and 562*+ means 5 + (6 * 2).

🎯 Goal: Build a program that uses a stack to evaluate a postfix expression containing single-digit numbers and the operators +, -, *, and /.

📋 What You'll Learn

Create a string variable called postfix with the exact value 231*+9-.

Create an empty stack of integers called stack.

Use a for loop with variable ch to iterate over each character in postfix.

If ch is a digit, convert it to an integer and push it onto stack.

If ch is an operator (+, -, *, /), pop the top two integers from stack, apply the operator, and push the result back onto stack.

After the loop, print the top value of stack as the final result.

💡 Why This Matters

🌍 Real World

Postfix expressions are used in calculators and computer programs to simplify expression evaluation without parentheses.

💼 Career

Understanding stacks and expression evaluation is important for software developers working on compilers, calculators, and interpreters.

1

Create the postfix expression string

Create a string variable called postfix and set it to the exact value "231*+9-".

DSA C++

# Create the postfix expression string
# Your code here

Hint

Use std::string postfix = "231*+9-"; to create the string.

2

Create an empty stack of integers

Create an empty stack of integers called stack using std::stack<int>.

DSA C++

std::string postfix = "231*+9-";
// Create an empty stack of integers called stack
# Your code here

Hint

Use std::stack<int> stack; to create the stack.

3

Iterate over the postfix string and process characters

Use a for loop with variable ch to iterate over each character in postfix. Inside the loop, if ch is a digit, convert it to an integer and push it onto stack. If ch is an operator (+, -, *, /), pop the top two integers from stack, apply the operator, and push the result back onto stack.

DSA C++

std::string postfix = "231*+9-";
std::stack stack;
// Use a for loop with variable ch to iterate over postfix
// If ch is a digit, push it as int onto stack
// If ch is an operator, pop two values, apply operator, push result
# Your code here

Hint

Use for (char ch : postfix) to loop. Use std::isdigit(ch) to check digits. Use stack.top() and stack.pop() to get values. Apply operators with if-else.

4

Print the final result from the stack

Print the top value of stack using std::cout as the final result.

DSA C++

std::string postfix = "231*+9-";
std::stack stack;

for (char ch : postfix) {
    if (std::isdigit(ch)) {
        stack.push(ch - '0');
    } else {
        int val2 = stack.top();
        stack.pop();
        int val1 = stack.top();
        stack.pop();
        int result = 0;
        if (ch == '+') result = val1 + val2;
        else if (ch == '-') result = val1 - val2;
        else if (ch == '*') result = val1 * val2;
        else if (ch == '/') result = val1 / val2;
        stack.push(result);
    }
}
// Print the final result from stack
# Your code here

Hint

Use std::cout << stack.top() << std::endl; to print the final result.

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