Evaluate Postfix Expression Using Stack in DSA Java - Time & Space Complexity

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to evaluate a postfix expression changes as the expression gets longer.

Specifically, how does the number of steps grow when we process more symbols in the expression?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public 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 b = stack.pop();
            int a = stack.pop();
            switch (c) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/': stack.push(a / b); break;
            }
        }
    }
    return stack.pop();
}
    

This code evaluates a postfix expression by scanning each character, pushing numbers, and applying operators using a stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each character of the expression once.
• How many times: Exactly once for each character in the expression (n times).

How Execution Grows With Input

As the expression length grows, the number of steps grows directly with it.

Input Size (n)	Approx. Operations
10	About 10 steps (one per character)
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows in a straight line with input size; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows linearly with the length of the postfix expression.

Common Mistake

[X] Wrong: "Because we pop twice and push once for operators, the time is more than linear, maybe quadratic."

[OK] Correct: Each character is processed once, and stack operations are constant time, so total steps still grow linearly.

Interview Connect

Understanding this linear time complexity helps you explain how stack-based evaluation is efficient and predictable, a key skill in coding interviews.

Self-Check

"What if the expression included multi-digit numbers separated by spaces? How would the time complexity change?"

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