46-Expression-Evaluation.md

Expression Evaluation

Problem Link

Practice Problem

---

Pattern

• Stack
• Parsing

---

Approach

Parse the expression character by character, applying precedence rules and collapsing partial results with stacks.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int evaluate(String s) {
        Stack<Integer> values = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int num = 0;
        boolean building = false;
        for (int i = 0; i <= s.length(); i++) {
            char c = i == s.length() ? '+' : s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
                building = true;
            } else if (c == ' ') {
                continue;
            } else {
                if (building) {
                    values.push(num);
                    num = 0;
                    building = false;
                }
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(c)) apply(values, ops.pop());
                ops.push(c);
            }
        }
        while (!ops.isEmpty()) apply(values, ops.pop());
        return values.pop();
    }

    private int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }

    private void apply(Stack<Integer> values, char op) {
        int b = values.pop();
        int a = values.pop();
        if (op == '+') values.push(a + b);
        else if (op == '-') values.push(a - b);
        else if (op == '*') values.push(a * b);
        else values.push(a / b);
    }
}