Evaluate Postfix Expression Using Stack in DSA Java - Build from Scratch

Evaluate Postfix Expression Using Stack

📖 Scenario: You are building a simple calculator that reads a postfix expression (also called Reverse Polish Notation) and calculates the result. Postfix expressions have operators after their operands, like 23+ which means 2 + 3.Using a stack helps to solve this easily by pushing numbers and applying operators step-by-step.

🎯 Goal: Build a Java program that uses a stack to evaluate a postfix expression containing single-digit numbers and the operators +, -, *, and /.

📋 What You'll Learn

Create a stack to hold integer values

Use a loop to process each character in the postfix expression

Push numbers onto the stack

Pop two numbers when an operator is found and apply the operator

Push the result back onto the stack

Print the final result after processing the entire expression

💡 Why This Matters

🌍 Real World

Postfix expression evaluation is used in calculators and compilers to simplify expression parsing and calculation.

💼 Career

Understanding stacks and expression evaluation is important for software developers working on interpreters, calculators, and language processing tools.

1

Create the postfix expression string

Create a String variable called postfix and set it to the exact value "231*+9-".

DSA Java

# Your code here

Hint

This string represents the postfix expression to evaluate.

2

Create a stack to hold integers

Create a Stack<Integer> called stack using new Stack<>().

DSA Java

String postfix = "231*+9-";
// Create the stack here
# Your code here

Hint

Use Stack<Integer> stack = new Stack<>(); to create the stack.

3

Process each character and evaluate

Use a for loop with int i = 0; i < postfix.length(); i++ to iterate over postfix. Inside the loop, get the character at i with postfix.charAt(i). If the character is a digit, push its integer value onto stack. If it is an operator (+, -, *, /), pop two integers from stack, apply the operator (second popped operand first), and push the result back onto stack.

DSA Java

import java.util.Stack;

String postfix = "231*+9-";
Stack stack = new Stack();

// Add the for loop and evaluation logic below
# Your code here

Hint

Remember to pop the second operand first, then the first operand, before applying the operator.

4

Print the final result

Print the top value of stack using System.out.println(stack.pop()).

DSA Java

import java.util.Stack;

String postfix = "231*+9-";
Stack stack = new Stack();

for (int i = 0; i < postfix.length(); i++) {
    char ch = postfix.charAt(i);
    if (Character.isDigit(ch)) {
        stack.push(ch - '0');
    } else {
        int b = stack.pop();
        int a = stack.pop();
        int result = 0;
        switch (ch) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = a / b;
                break;
        }
        stack.push(result);
    }
}

// Print the final result
# Your code here

Hint

The final result of the expression 231*+9- is -4.

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