Evaluate Postfix Expression Using Stack in DSA Java

Mental Model

Use a stack to keep numbers until an operator appears, then combine the last two numbers with that operator.

Analogy: Imagine a chef stacking ingredients on a plate. When the chef gets a cooking instruction (operator), they take the last two ingredients, cook them together, and put the result back on the plate.

Stack (top at right): []
Postfix expression: 2 3 + 4 *

Initial stack empty, reading left to right.

Dry Run Walkthrough

Input: Postfix expression: 2 3 + 4 *

Goal: Calculate the final value of the postfix expression using a stack.

Step 1: Read '2', push onto stack

Stack: [2]

Why: Numbers are pushed to stack to wait for operators

Step 2: Read '3', push onto stack

Stack: [2, 3]

Why: Keep numbers until operator appears

Step 3: Read '+', pop 3 and 2, add them (2+3=5), push result

Stack: [5]

Why: Operator means combine last two numbers and push result

Step 4: Read '4', push onto stack

Stack: [5, 4]

Why: Push number to stack

Step 5: Read '*', pop 4 and 5, multiply (5*4=20), push result

Stack: [20]

Why: Operator combines last two numbers again

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA Java

import java.util.Stack;

public class PostfixEvaluator {

    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            if (Character.isWhitespace(ch)) {
                continue; // skip spaces
            }

            if (Character.isDigit(ch)) {
                // Convert char digit to int and push
                stack.push(ch - '0');
            } else {
                // Operator: pop two operands
                int val2 = stack.pop();
                int val1 = stack.pop();

                switch (ch) {
                    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 = "2 3 + 4 *";
        int result = evaluatePostfix(expr);
        System.out.println(result);
    }
}

stack.push(ch - '0');

Push numeric value of digit character onto stack

int val2 = stack.pop();

Pop second operand for operation

int val1 = stack.pop();

Pop first operand for operation

stack.push(val1 + val2);

Push result of addition back to stack

stack.push(val1 - val2);

Push result of subtraction back to stack

stack.push(val1 * val2);

Push result of multiplication back to stack

stack.push(val1 / val2);

Push result of division back to stack

Output

20

Complexity Analysis

Time: O(n) because we scan the expression once, processing each character.

Space: O(n) because in worst case all characters are numbers pushed onto the stack.

vs Alternative: Compared to evaluating infix expressions which require operator precedence handling and possibly two stacks, postfix evaluation is simpler and faster.

Edge Cases

Empty expression

Returns error or empty stack pop exception

DSA Java

No explicit guard; stack.pop() will throw exception if empty

Expression with single number only

Returns that number as result

DSA Java

stack.push(ch - '0');

Division by zero

Throws ArithmeticException at division

DSA Java

stack.push(val1 / val2);

When to Use This Pattern

When you see an expression with operators after operands and no parentheses, use the stack evaluation pattern for postfix expressions because it handles operations in correct order without precedence rules.

Common Mistakes

Mistake: Popping operands in wrong order causing incorrect subtraction or division results.
Fix: Always pop second operand first, then first operand, so operations like val1 - val2 are correct.

Mistake: Not skipping spaces causing errors when reading expression.
Fix: Add a check to skip whitespace characters before processing.

Summary

Evaluates a postfix expression by using a stack to store operands and applying operators to the last two operands.

Use it when you need to calculate the value of postfix expressions efficiently without worrying about operator precedence.

The key insight is to push numbers on the stack and when an operator appears, pop the last two numbers, combine them, and push the result back.

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