Evaluate Postfix Expression Using Stack in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Expression Evaluation

What is the output of the following C++ code that evaluates a postfix expression using a stack?

DSA C++

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

int evaluatePostfix(string expr) {
    stack<int> s;
    for (char c : expr) {
        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() {
    string expr = "231*+9-";
    cout << evaluatePostfix(expr) << endl;
    return 0;
}

A Output: 0

B Output: 2

C Output: 8

D Output: -4

💡 Hint

Trace the stack operations step-by-step for each character in the expression.

The postfix expression "231*+9-" evaluates as follows: push 2, push 3, push 1, multiply top two (3*1=3), push result, add top two (2+3=5), push 9, subtract top two (5-9=-4). Final result is -4.

❓ Predict Output

intermediate

Result of Postfix Expression with Division

What is the output of this C++ code evaluating the postfix expression "82/3-"?

DSA C++

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

int evaluatePostfix(string expr) {
    stack<int> s;
    for (char c : expr) {
        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() {
    string expr = "82/3-";
    cout << evaluatePostfix(expr) << endl;
    return 0;
}

A Output: 1

B Output: 2

C Output: 0

D Output: 3

💡 Hint

Remember integer division truncates towards zero in C++.

The expression "82/3-" evaluates as: push 8, push 2, divide (8/2=4), push 3, subtract (4-3=1). Final result is 1.

🔧 Debug

advanced

Identify the Runtime Error in Postfix Evaluation

What runtime error will occur when running this C++ code with input "3+"?

DSA C++

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

int evaluatePostfix(string expr) {
    stack<int> s;
    for (char c : expr) {
        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() {
    string expr = "3+";
    cout << evaluatePostfix(expr) << endl;
    return 0;
}

A Runtime error: stack underflow (pop from empty stack)

B Runtime error: invalid character in expression

C Runtime error: division by zero

D No runtime error, output is 35

💡 Hint

Check how many operands are available before each operator is applied.

Processing '3+': push 3 (stack: [3]). For '+': pop val2 = 3 (stack empty), then attempt to pop val1 from empty stack causes runtime error: stack underflow.

❓ Predict Output

advanced

Output of Complex Postfix Expression

What is the output of this C++ code evaluating the postfix expression "562+*84/-"?

DSA C++

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

int evaluatePostfix(string expr) {
    stack<int> s;
    for (char c : expr) {
        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() {
    string expr = "562+*84/-";
    cout << evaluatePostfix(expr) << endl;
    return 0;
}

A Output: 2

B Output: 38

C Output: 40

D Output: 42

💡 Hint

Evaluate step-by-step: push digits, apply operators in order.

Stepwise evaluation: - push 5 (stack: [5]) - push 6 ([5,6]) - push 2 ([5,6,2]) - '+' : 6+2=8 ([5,8]) - '*' : 5*8=40 ([40]) - push 8 ([40,8]) - push 4 ([40,8,4]) - '/' : 8/4=2 ([40,2]) - '-' : 40-2=38 ([38]) Final result is 38.

🧠 Conceptual

expert

Stack Size During Postfix Evaluation

Given the postfix expression "345+*62/-", what is the maximum size of the stack during its evaluation?

A Maximum stack size is 4

B Maximum stack size is 5

C Maximum stack size is 3

D Maximum stack size is 6

💡 Hint

Count how many operands are pushed before each operator reduces the stack size.

Stepwise stack sizes: - push 3 (1) - push 4 (2) - push 5 (3) - '+' (pop 2, push 1: 2) - '*' (pop 2, push 1: 1) - push 6 (2) - push 2 (3) - '/' (pop 2, push 1: 2) - '-' (pop 2, push 1: 1) Maximum size is 3.

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