Problem statement

Evaluate the arithmetic expression s and return its value. Do not use any built-in function that evaluates strings as code.

s contains non-negative integers, the operators + and -, parentheses ( ), and spaces (which mean nothing). - may also be used as a unary minus — at the very start of the expression or right after (, as in -5 or -(2 + 3) — but + is never unary, and two operators never appear next to each other.

Example 1

Input: s = "7 - (3 + 2)"
Output: 2

Example 2

Input: s = "-(4 - 10) + 1"
Output: 7
Explanation: The unary minus negates the whole bracket: -(-6) + 1.

Example 3

Input: s = "(12+(3-(5+1)))-(20)"
Output: -11

Constraints

• 1 <= s.length <= 3 * 10^5
• s consists of digits, '+', '-', '(', ')' and ' '
• s is a valid expression
• Every number and every intermediate result fits in a signed 32-bit integer

Hints for Basic Calculator

1. Hint 1

   Without parentheses the answer is just a running sum: each number is added with the sign in front of it.

2. Hint 2

   A parenthesised group is its own running sum, which is then added to the outer sum with the sign in front of the (.

3. Hint 3

   On (, push the current result and sign onto a stack and start fresh; on ), finish the inner sum and combine: result = savedResult + savedSign * result.

How to solve Basic Calculator

With only + and -, an expression is a signed sum. Parentheses nest sums, so keep a stack of the outer (result, sign) pairs that are waiting for an inner sum to finish.

Approach

1. Keep result = 0, sign = 1, num = 0 and an empty stack. Skip spaces.
2. Digit: num = num * 10 + digit.
3. + or -: add sign * num to result, reset num, and set sign to +1 or -1.
4. (: push result and sign, then reset result = 0, sign = 1.
5. ): add sign * num to result, reset num, pop the saved sign and result, and set result = savedResult + savedSign * result.
6. At the end return result + sign * num.

Why it works

Between parentheses the algorithm maintains the invariant value so far = result + sign * num. A ( suspends the outer sum exactly as it stood, including the sign that applies to the whole group, so the inner sum can be computed from scratch and then folded in with that sign. A unary minus needs no special case: at the start of a group result is 0, so -x is evaluated as 0 - x.

Complexity

• Time — O(n)
• Space — O(n) for the stack of nested groups

Pitfalls

• Numbers have several digits — accumulate them instead of reading one character.
• Flush the pending number before handling ) and at the end of the string.
• A unary minus before ( must negate the whole group, which the saved sign handles automatically.

Reference solution

Python

def calculate(s: str) -> int:
    result = 0
    sign = 1
    num = 0
    st = []
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '+' or c == '-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':
            st.append(result)
            st.append(sign)
            result = 0
            sign = 1
        elif c == ')':
            result += sign * num
            num = 0
            saved_sign = st.pop()
            saved_result = st.pop()
            result = saved_result + saved_sign * result
    return result + sign * num

Java

public static int calculate(String s) {
    long result = 0, num = 0;
    int sign = 1;
    Deque<Long> st = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
        } else if (c == '+' || c == '-') {
            result += sign * num;
            num = 0;
            sign = c == '+' ? 1 : -1;
        } else if (c == '(') {
            st.push(result);
            st.push((long) sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * num;
            num = 0;
            long savedSign = st.pop();
            long savedResult = st.pop();
            result = savedResult + savedSign * result;
        }
    }
    return (int) (result + sign * num);
}

C++

int calculate(string s) {
    long long result = 0, num = 0;
    int sign = 1;
    vector<long long> st;
    for (char c : s) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
        } else if (c == '+' || c == '-') {
            result += sign * num;
            num = 0;
            sign = c == '+' ? 1 : -1;
        } else if (c == '(') {
            st.push_back(result);
            st.push_back(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * num;
            num = 0;
            long long savedSign = st.back(); st.pop_back();
            long long savedResult = st.back(); st.pop_back();
            result = savedResult + savedSign * result;
        }
    }
    return (int)(result + sign * num);
}

JavaScript

var calculate = function(s) {
    var result = 0, sign = 1, num = 0, st = [];
    for (var i = 0; i < s.length; i++) {
        var c = s[i];
        if (c >= "0" && c <= "9") {
            num = num * 10 + (c.charCodeAt(0) - 48);
        } else if (c === "+" || c === "-") {
            result += sign * num;
            num = 0;
            sign = c === "+" ? 1 : -1;
        } else if (c === "(") {
            st.push(result, sign);
            result = 0;
            sign = 1;
        } else if (c === ")") {
            result += sign * num;
            num = 0;
            var savedSign = st.pop();
            var savedResult = st.pop();
            result = savedResult + savedSign * result;
        }
    }
    return result + sign * num;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Subtraction in Linked List Hard
• GCD Sort of an Array Hard
• Count Valid Paths in a Tree Hard
• Create Components With Same Value Hard
• Cat and Mouse Hard
• Find the Number of Subsequences With Equal GCD Hard