299. Basic Calculator III

Scan the expression maintaining a stack of terms. Apply the pending operator when the next operator (or end) is reached: push for +/-, and combine with the top for * and / (which bind tighter). A '(' recurses to evaluate the sub-expression as a single number.

One stack, respecting precedence

Walk left to right building an integer num. Remember the operator op that preceded num (start with +). When you hit the next operator, a ) or the end, resolve num using op:

• +: push num
• -: push -num
• *: pop top, push top * num
• /: pop top, push trunc(top / num)

At the end, the answer is the sum of the stack — the * and / were already folded into their operands, so only additive terms remain.

Parentheses are handled by recursion: on (, recursively evaluate until the matching ) and treat the returned value as num.

def eval(iterator):
    stack = []; num = 0; op = '+'
    for ch in iterator:
        if ch is digit: num = num*10 + int(ch)
        elif ch == '(': num = eval(iterator)     # sub-expression value
        elif ch in '+-*/)' or end:
            apply op to (stack, num)
            op = ch; num = 0
            if ch == ')': break
    return sum(stack)

Worked example

s = "2*(5+5*2)/3+(6/2+8)".

• (5+5*2) → 5 + 10 = 15.
• 2*15/3 → 30/3 = 10.
• (6/2+8) → 3 + 8 = 11.
• 10 + 11 = 21.

Result 21.

Complexity

• Time: O(n).
• Space: O(n) for the stack and recursion depth.

class Solution {
    public int calculate(String s) {
        int[] pos = {0};
        return eval(s.replaceAll(" ", ""), pos);
    }

    private int eval(String s, int[] pos) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char op = '+';
        while (true) {
            char ch = pos[0] < s.length() ? s.charAt(pos[0]) : ';';
            pos[0]++;
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            } else if (ch == '(') {
                num = eval(s, pos);
            } else {  // operator, ')', or end
                switch (op) {
                    case '+': stack.push(num); break;
                    case '-': stack.push(-num); break;
                    case '*': stack.push(stack.pop() * num); break;
                    case '/': stack.push(stack.pop() / num); break;  // truncates toward zero
                }
                op = ch;
                num = 0;
                if (ch == ')' || ch == ';') break;
            }
        }
        int sum = 0;
        for (int x : stack) sum += x;
        return sum;
    }
}