Evaluate Postfix Expression Using Stack in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a postfix expression?

A postfix expression is a mathematical notation where the operator comes after the operands. For example, instead of writing 3 + 4, we write 3 4 +.

beginner

Why do we use a stack to evaluate postfix expressions?

We use a stack because it helps keep track of operands. When we see an operator, we pop the last two operands, apply the operator, and push the result back. This matches the postfix order naturally.

beginner

What happens when you encounter an operand in postfix evaluation?

When you see an operand (a number), you push it onto the stack to use later when an operator appears.

intermediate

What is the step-by-step process to evaluate the postfix expression '5 3 2 * + 9 -'?

1. Push 5
2. Push 3
3. Push 2
4. '*' operator: pop 2 and 3, multiply (3*2=6), push 6
5. '+' operator: pop 6 and 5, add (5+6=11), push 11
6. Push 9
7. '-' operator: pop 9 and 11, subtract (11-9=2), push 2
Result is 2.

intermediate

What error can occur if the postfix expression is invalid during evaluation?

If the expression is invalid, you might try to pop from an empty stack or have leftover operands after evaluation. This means the expression is not well-formed.

In postfix evaluation, what do you do when you see an operator?

A Push the operator onto the stack

B Pop two operands, apply the operator, push the result

C Ignore the operator

D Pop one operand and push it back

When an operator appears, pop the last two operands, apply the operator, then push the result back.

What is the result of evaluating the postfix expression '2 3 + 4 *'?

A 20

B 8

C 10

D 14

2 + 3 = 5, then 5 * 4 = 20. So the correct answer is 20 (Option A).

Which data structure is best suited for evaluating postfix expressions?

A Queue

B Linked List

C Stack

D Array

Stack is best because it allows easy access to the last operands needed for operators.

What should you do if the stack has more than one element after evaluating the postfix expression?

A Pop all elements

B The expression is valid

C Push more operands

D The expression is invalid

More than one element means the expression was not well-formed or fully evaluated.

In postfix notation, where is the operator placed?

A After the operands

B Before the operands

C Between the operands

D At the end of the expression only

In postfix notation, the operator comes after its operands.

Explain how to evaluate a postfix expression using a stack.

Think about what happens step-by-step when you read each symbol.

Describe common errors that can happen when evaluating postfix expressions.

Consider what happens if the expression is not correct.

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