178. Basic Calculator

Scan left to right accumulating a running result and the sign of the next number. When you meet '(', push the current result and sign, then start fresh; when you meet ')', fold the sub-result back using the pushed sign and result.

Idea

With only +, -, and parentheses, we never need operator precedence — just a running total and the current sign. Parentheses introduce nested contexts, so a stack saves the outer result and sign before entering, and restores them on exit.

Algorithm

Scan each character, building number from digits:

• On + / -: add sign * number to result, reset number, set sign to +1 / -1.
• On (: push result then sign; reset result = 0, sign = 1 (new context).
• On ): add sign * number to result; multiply result by the popped sign, then add the popped outer result.

After the scan, add the final sign * number.

Worked example: (1+(4+5+2)-3)+(6+8)

The inner (4+5+2)=11; then (1+11-3)=9; then (6+8)=14; total 23.

Complexity

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

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int result = 0;
        int number = 0;
        int sign = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                number = number * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * number;
                number = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * number;
                number = 0;
                sign = -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * number;
                number = 0;
                result *= stack.pop();
                result += stack.pop();
            }
        }
        return result + sign * number;
    }
}