Stack Evaluate Expression Java

Direct Answer

Use a stack. For postfix (RPN): scan tokens, push numbers, and on an operator pop the top two operands, apply it, and push the result; the final stack value is the answer - O(n). For infix, either convert to postfix first (shunting-yard) or use two stacks (operands + operators) honoring operator precedence.

Deep Dive & Architecture

A postfix expression puts each operator after its operands, so a stack can evaluate it without parentheses or precedence rules. Push numbers as they appear. On an operator, pop the right operand first, then the left operand, apply the operator, and push the result.

Worked example: 2 3 4 * +

Push 2, 3, and 4. * pops right 4 and left 3, then pushes 12. + pops right 12 and left 2, then pushes 14. At the end, exactly one value remains, so the result is 14.

Operand order matters for subtraction and division. For 8 2 /, popping gives right 2 and left 8, so the calculation is 8 / 2, not 2 / 8.

For an ordinary infix expression such as 2 + 3 * 4, a second operator stack or a conversion to postfix is needed to handle precedence, associativity, and parentheses. Tokens should be parsed rather than assuming every number has one digit. Invalid input includes too few operands for an operator or more than one value left after all tokens are processed.

Each token is pushed or popped a constant number of times, so postfix evaluation is O(n) time and O(n) stack space in the worst case.

Code Example

int evalRPN(String[] tokens) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+", "-", "*", "/" -> {
                int b = st.pop();          // right operand (popped first)
                int a = st.pop();          // left operand
                st.push(switch (t) {
                    case "+" -> a + b;  case "-" -> a - b;
                    case "*" -> a * b;  default -> a / b;
                });
            }
            default -> st.push(Integer.parseInt(t));
        }
    }
    return st.pop();
}

// {"2","3","+","4","*"}: push2,push3,+ ->5, push4,* ->20 -> 20

Common Mistakes & Pitfalls

• Operand order: for -//, the second pop is the left operand; swapping gives wrong results.
• Infix without precedence: evaluating 3 + 4 * 2 left to right ignores that * binds tighter.
• Empty stack / malformed input: too few operands means an invalid expression.
• Integer division/overflow: be aware of truncation and large intermediate values.