Evaluation of Postfix Expression

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Stack-based evaluation: push operands, on operator pop two operands, apply, push result.

Algorithm

1Scan tokens left to right.
2If token is number: push to stack.
3If token is operator (+,-,*,/): pop b then a, compute a op b, push result.
4Final stack top is the result.

Example Walkthrough

Input: "2 3 1 * + 9 -"

1.Push 2,3,1. *: pop 3,1â†’3. +: pop 2,3â†’5. Push 9. -: pop 5,9â†’-4.

Output: -4

Common Pitfalls

•Pop order matters: pop b first, then a, compute a op b (not b op a).

Evaluation of Postfix Expression.java

Java

// Approach: Stack-based evaluation. Push operands; on operator, pop two values, apply op, push result.
// Time: O(n) Space: O(n)
class Solution {
    public int evaluate(String[] arr) {
        Deque<Integer> operands = new ArrayDeque<>();
        int num1 = 0, num2 = 0;
        for (String el : arr) {

            if (el.equals("+") || el.equals("-") || el.equals("*") || el.equals("/")) {
                num2 = operands.pop();
                num1 = operands.pop();
            }

            if (el.equals("+"))
                operands.push(num1 + num2);
            else if (el.equals("-"))
                operands.push(num1 - num2);
            else if (el.equals("*"))
                operands.push(num1 * num2);
            else if (el.equals("/"))
                operands.push(num1 / num2);
            else
                operands.push(Integer.parseInt(el));
        }

        return operands.peek();
    }
}

Was this solution helpful?