Postfix Evaluation

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Evaluate postfix (Reverse Polish Notation) expression. Stack-based evaluation.

Algorithm

1For each token: if operand push to stack. If operator: pop two operands, apply operator, push result.

Common Pitfalls

•Same as LC 150. Handle negative numbers. Division should truncate toward zero.

Postfix Evaluation.java

Java

// Approach: Stack-based. Push numbers; on operator pop two, evaluate, push result.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int evaluatePostfix(String[] arr) {
        Stack<Integer> stack = new Stack<>();

        for (String token : arr) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                int result = applyOperator(a, b, token);
                stack.push(result);
            } else
                stack.push(Integer.parseInt(token));
        }

        return stack.pop();
    }

    private static boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*")
                || s.equals("/") || s.equals("^");
    }

    private static int applyOperator(int a, int b, String op) {
        switch (op) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            case "/":
                return Math.floorDiv(a, b);
            case "^":
                return (int) Math.pow(a, b);
        }

        throw new IllegalArgumentException("Invalid operator: " + op);
    }
}

Was this solution helpful?