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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Expression Evaluation

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

DSA Java

import java.util.Stack;

public class PostfixEval {
    public static int evaluatePostfix(String expr) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                stack.push(c - '0');
            } else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                switch (c) {
                    case '+': stack.push(val1 + val2); break;
                    case '-': stack.push(val1 - val2); break;
                    case '*': stack.push(val1 * val2); break;
                    case '/': stack.push(val1 / val2); break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String expr = "231*+9-";
        System.out.println(evaluatePostfix(expr));
    }
}

A 2

B 7

C -4

D 8

💡 Hint

Trace the expression step-by-step using a stack: push digits, pop two for operators, apply operation, push result.

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

🧠 Conceptual

intermediate

Stack Usage in Postfix Evaluation

Why is a stack the best data structure to evaluate postfix expressions?

A Because it allows last-in, first-out access which matches the order of operations in postfix evaluation.

B Because it stores elements in sorted order automatically.

C Because it allows random access to any element quickly.

D Because it uses less memory than arrays.

💡 Hint

Think about how postfix expressions require you to use the most recent operands first.

Postfix evaluation requires using the most recently seen operands first when an operator appears. A stack provides last-in, first-out access, making it ideal for this.

❓ Predict Output

advanced

Output of Postfix Evaluation with Division

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

DSA Java

import java.util.Stack;

public class PostfixEvalDiv {
    public static int evaluatePostfix(String expr) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                stack.push(c - '0');
            } else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                switch (c) {
                    case '+': stack.push(val1 + val2); break;
                    case '-': stack.push(val1 - val2); break;
                    case '*': stack.push(val1 * val2); break;
                    case '/': stack.push(val1 / val2); break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String expr = "82/3-";
        System.out.println(evaluatePostfix(expr));
    }
}

A 0

B 3

C 2

D 1

💡 Hint

Remember integer division truncates towards zero in Java.

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

🔧 Debug

advanced

Identify the Error in Postfix Evaluation Code

What error will this Java code produce when evaluating the postfix expression "34+"?

DSA Java

import java.util.Stack;

public class PostfixEvalBug {
    public static int evaluatePostfix(String expr) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                stack.push(c - '0');
            } else {
                int val1 = stack.pop();
                int val2 = stack.pop();
                switch (c) {
                    case '+': stack.push(val1 + val2); break;
                    case '-': stack.push(val1 - val2); break;
                    case '*': stack.push(val1 * val2); break;
                    case '/': stack.push(val1 / val2); break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String expr = "34+";
        System.out.println(evaluatePostfix(expr));
    }
}

A Wrong output 7

B No error, output 7

C ArithmeticException

D EmptyStackException

💡 Hint

Check the order of popping operands for non-commutative operations.

The code pops val1 first (top of stack, second operand) then val2 (first operand), reversing the order. For '+', which is commutative, 4 + 3 = 3 + 4 = 7, so output is correct with no error. The reversed order would cause wrong results for non-commutative operators like '-' or '/'.

🧠 Conceptual

expert

Handling Multi-digit Numbers in Postfix Evaluation

Why does the simple stack-based postfix evaluation code fail for expressions with multi-digit numbers like "12 3 +"?

A Because it processes the expression character by character, treating each digit separately, not recognizing multi-digit numbers.

B Because stacks cannot store numbers larger than 9.

C Because postfix expressions cannot have multi-digit numbers.

D Because Java does not support multi-digit numbers in strings.

💡 Hint

Think about how the code reads each character and converts it to a number.

The code reads one character at a time and converts it to a digit, so multi-digit numbers split into separate digits and are treated as separate operands, causing incorrect evaluation.

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