181. Basic Calculator II

Process * and / immediately by popping the stack. Push results of + and - for later summation.

Approach

1. Parse numbers and operators.
2. For + and -, push number (with sign) to stack.
3. For * and /, pop top, compute, push result.
4. Sum the stack for the final answer.

Complexity

• Time: O(n)
• Space: O(n)

import java.util.*;

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char op = '+';

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.length() - 1) {
                if (op == '+') stack.push(num);
                else if (op == '-') stack.push(-num);
                else if (op == '*') stack.push(stack.pop() * num);
                else if (op == '/') stack.push(stack.pop() / num);
                op = c;
                num = 0;
            }
        }

        int result = 0;
        for (int n : stack) {
            result += n;
        }
        return result;
    }
}