Evaluate Postfix Expression Using Stack in DSA Java - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Start

↓

Read next token

↓

Is token a number?

Yes→Push number onto stack

No↓

Pop two numbers from stack

↓

Apply operator on popped numbers

↓

Push result back onto stack

↓

More tokens?

Yes→Read next token

No↓

Pop final result from stack

↓

End

We read each token from the postfix expression. If it is a number, push it on the stack. If it is an operator, pop two numbers, apply the operator, and push the result back. Repeat until all tokens are processed. The last number on the stack is the result.

Execution Sample

DSA Java

String expr = "231*+9-";
Stack<Integer> stack = new Stack<>();
for (char c : expr.toCharArray()) {
  if (Character.isDigit(c)) stack.push(c - '0');
  else {
    int b = stack.pop(); int a = stack.pop();
    stack.push(applyOp(a, b, c));
  }
}
int result = stack.pop();

This code evaluates the postfix expression "231*+9-" step-by-step using a stack.

Execution Table

Step	Operation	Token	Stack Before	Action	Stack After	Visual State
1	Read token	2	[]	Push 2	[2]	2 -> null
2	Read token	3	[2]	Push 3	[2, 3]	2 -> 3 -> null
3	Read token	1	[2, 3]	Push 1	[2, 3, 1]	2 -> 3 -> 1 -> null
4	Read token	*	[2, 3, 1]	Pop 1 and 3, multiply 3*1=3, push 3	[2, 3]	2 -> 3 -> null
5	Read token	+	[2, 3]	Pop 3 and 2, add 2+3=5, push 5	[5]	5 -> null
6	Read token	9	[5]	Push 9	[5, 9]	5 -> 9 -> null
7	Read token	-	[5, 9]	Pop 9 and 5, subtract 5-9=-4, push -4	[-4]	-4 -> null
8	End		[-4]	Pop final result	[]	empty stack

💡 All tokens processed; final result popped from stack.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
stack	[]	[2]	[2,3]	[2,3,1]	[2,3]	[5]	[5,9]	[-4]	[]
token	N/A	'2'	'3'	'1'	'*'	'+'	'9'	'-'	N/A
result	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A	-4

Key Moments - 3 Insights

Why do we pop two numbers from the stack when we see an operator?

Because postfix operators apply to the two most recent numbers. The execution_table rows 4, 5, and 7 show popping two numbers before applying the operator.

Why is the first popped number the second operand and the second popped number the first operand?

Stack is LIFO. The last pushed number is the right operand. For example, in row 4, popping 1 then 3 means 3 is first operand, 1 second operand for multiplication.

What happens if the expression is empty or invalid?

The stack will be empty or have incorrect number of elements. The exit_note and final stack state in row 8 show normal completion only if expression is valid.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the stack after applying the '+' operator?

A [2, 3]

B [5]

C [2, 3, 5]

D [3, 5]

💡 Hint

Check the 'Stack After' column in row 5 of execution_table.

At which step does the stack first contain only one element?

A Step 5

B Step 3

C Step 7

D Step 8

💡 Hint

Look at the 'Stack After' column and find when stack size is 1 for the first time.

If the token '9' at step 6 was missing, what would be the stack after step 7?

A [-4]

B [5]

C Error due to insufficient operands

D [5, 9]

💡 Hint

Refer to the 'Action' column at step 7 and consider how many operands are needed.

Concept Snapshot

Evaluate Postfix Expression Using Stack:
- Read tokens left to right
- Push numbers onto stack
- On operator, pop two numbers, apply operator, push result
- Final stack top is result
- Works because postfix order matches operand/operator sequence

Full Transcript

To evaluate a postfix expression, we use a stack. We read each token from left to right. If the token is a number, we push it onto the stack. If it is an operator, we pop two numbers from the stack, apply the operator, and push the result back. We repeat this until all tokens are processed. The last number left on the stack is the final result. This method works because postfix expressions list operands before their operators, allowing easy evaluation with a stack.

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