Evaluate Postfix Expression Using Stack in DSA Java - 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 us 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 last-in, first-out nature of stacks.

beginner

What happens when you encounter an operand in a postfix expression during 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 '2 3 1 * + 9 -'?

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

intermediate

What will be the output of evaluating the postfix expression '5 6 2 + * 12 4 / -'?

Step-by-step:
Push 5
Push 6
Push 2
Operator '+': pop 2 and 6, add 8, push 8
Operator '*': pop 8 and 5, multiply 40, push 40
Push 12
Push 4
Operator '/': pop 4 and 12, divide 3, push 3
Operator '-': pop 3 and 40, subtract 37, push 37
Result is 37.

What data structure is best suited to evaluate postfix expressions?

A Array

B Queue

C Stack

D Linked List

Stack is best because it allows last-in, first-out operations needed for postfix evaluation.

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

A Push it onto the stack

B Pop two operands, apply operator, push result

C Ignore it

D Pop one operand and push it back

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

What is the result of evaluating the postfix expression '4 5 + 7 *'?

A 48

B 33

C None of the above

D 63

4 + 5 = 9, then 9 * 7 = 63.

Which of these is NOT a valid step in postfix evaluation?

A Pop operator from stack

B Pop two operands for operator

C Push result back onto stack

D Push operand onto stack

Operators are not pushed or popped from the stack; only operands and results are.

If the postfix expression is '8 2 / 3 -', what is the final result?

A 1

B 4

C 5

D 2

8 / 2 = 4, then 4 - 3 = 1.

Explain how to evaluate a postfix expression using a stack.

Think about how you handle numbers and operators step by step.

Describe why postfix expressions do not need parentheses for evaluation.

Consider how the position of operators affects calculation order.

Practice

1. What is the main data structure used to evaluate a postfix expression?

easy

A. Queue

B. Array

C. Stack

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 result is pushed back.

3. Final Answer:

   Stack -> Option C

4. Quick Check:

   Postfix evaluation uses stack [OK]

Hint: Remember: postfix uses stack to hold operands [OK]

Common Mistakes:

• Confusing stack with queue
• Thinking array directly evaluates postfix
• Using linked list instead of stack

2. Which of the following Java code snippets correctly pushes an integer onto a stack named stack?

easy

A. stack.add(5);

B. stack.push(5);

C. stack.insert(5);

D. stack.enqueue(5);

Solution

1. Step 1: Recall Java Stack methods

   The Stack class in Java uses the method push() to add elements to the top.

2. Step 2: Identify correct method usage

   stack.push(5); correctly pushes integer 5 onto the stack.

3. Final Answer:

   stack.push(5); -> Option B

4. Quick Check:

   Use push() to add to stack [OK]

Hint: Use push() to add elements to stack in Java [OK]

Common Mistakes:

• Using add() which is for lists
• Using insert() which is invalid for stack
• Using enqueue() which is for queues

3. What is the output of the following Java code that evaluates the postfix expression "23+5*"?

import java.util.Stack;

public class PostfixEval {
    public static int evaluate(String expr) {
        Stack<Integer> stack = new Stack<>();
        for (char ch : expr.toCharArray()) {
            if (Character.isDigit(ch)) {
                stack.push(ch - '0');
            } else {
                int b = stack.pop();
                int a = stack.pop();
                switch (ch) {
                    case '+': stack.push(a + b); break;
                    case '*': stack.push(a * b); break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(evaluate("23+5*"));
    }
}

medium

A. 10

B. 15

C. Error

D. 25

Solution

1. Step 1: Evaluate postfix "23+5*" step-by-step

   Push 2, push 3, then '+' pops 3 and 2, adds to 5, push 5. Then push 5, '*' pops 5 and 5, multiplies to 25, push 25.

2. Step 2: Final stack pop

   Pop final result 25 from stack and print.

3. Final Answer:

   25 -> Option D

4. Quick Check:

   (2+3)*5 = 25 [OK]

Hint: Calculate stepwise: push digits, pop two for operator [OK]

Common Mistakes:

• Mixing operand order in subtraction/division
• Forgetting to convert char to int
• Not popping operands in correct order

4. Identify the error in the following Java code snippet that evaluates postfix expressions:

Stack<Integer> stack = new Stack<>();
for (char ch : expr.toCharArray()) {
    if (Character.isDigit(ch)) {
        stack.push(ch);
    } else {
        int b = stack.pop();
        int a = stack.pop();
        if (ch == '+') {
            stack.push(a + b);
        }
    }
}

medium

A. Pushing char directly instead of integer value

B. Using == to compare characters

C. Not handling other operators

D. Stack not initialized

Solution

1. Step 1: Check how digits are pushed

   The code pushes ch directly, which is a char, not its integer value.

2. Step 2: Correct way to push integer value

   Must convert char digit to int by ch - '0' before pushing.

3. Final Answer:

   Pushing char directly instead of integer value -> Option A

4. Quick Check:

   Push integer, not char [OK]

Hint: Convert char digit to int before pushing [OK]

Common Mistakes:

• Pushing char instead of int
• Ignoring other operators is not error here
• Using == for char comparison is valid

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

hard

A. 4

B. 0

C. -4

D. 2

Solution

1. Step 1: Evaluate postfix "82/3-4*" stepwise

   Push 8, push 2, '/' pops 2 and 8, 8/2=4 push 4. Push 3, '-' pops 3 and 4, 4-3=1 push 1. Push 4, '*' pops 4 and 1, 1*4=4 push 4.

2. Step 2: Re-check operator order and final pop

   Wait, subtraction order is a - b, so 4 - 3 = 1, then multiply by 4 = 4. Final result is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   (8/2 - 3) * 4 = 4 [OK]

Hint: Remember operator order: a op b, pop b then a [OK]

Common Mistakes:

• Reversing operand order in division or subtraction
• Forgetting to pop operands in correct order
• Misinterpreting operators precedence