Basic Calculator — DSA · Engineering Playbook

Problem#

Implement a calculator for an expression string containing digits, +, -, (, ), and spaces. No multiplication, division, or unary functions. Return the integer result.

Examples#

"1 + 1" → 2
" 2-1 + 2 " → 3
"(1+(4+5+2)-3)+(6+8)" → 23

Constraints#

1 <= s.length <= 3 * 10^5. The expression is always valid.

Approach#

Sweep the string. Maintain result (running sum) and sign (+1 or -1 to apply to the next number). On (, push (result, sign) and reset. On ), pop (savedResult, savedSign) and update result = savedResult + savedSign * result. Read multi-digit numbers, applying the current sign.

Solution#

class Solution {
public:
    int calculate(string s) {
        stack<pair<int,int>> st;
        long result = 0;
        int sign = 1;
        int i = 0, n = s.size();
        while (i < n) {
            char c = s[i];
            if (isdigit(c)) {
                long num = 0;
                while (i < n && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    ++i;
                }
                result += sign * num;
                continue;
            }
            if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') {
                st.push({(int)result, sign});
                result = 0; sign = 1;
            } else if (c == ')') {
                auto [savedRes, savedSign] = st.top(); st.pop();
                result = savedRes + savedSign * result;
            }
            ++i;
        }
        return (int)result;
    }
};

func calculate(s string) int {
    type frame struct{ res, sign int }
    st := []frame{}
    result := 0
    sign := 1
    i, n := 0, len(s)
    for i < n {
        c := s[i]
        if c >= '0' && c <= '9' {
            num := 0
            for i < n && s[i] >= '0' && s[i] <= '9' {
                num = num*10 + int(s[i]-'0')
                i++
            }
            result += sign * num
            continue
        }
        switch c {
        case '+':
            sign = 1
        case '-':
            sign = -1
        case '(':
            st = append(st, frame{result, sign})
            result = 0
            sign = 1
        case ')':
            top := st[len(st)-1]
            st = st[:len(st)-1]
            result = top.res + top.sign*result
        }
        i++
    }
    return result
}

class Solution:
    def calculate(self, s: str) -> int:
        st: list[tuple[int, int]] = []
        result = 0
        sign = 1
        i, n = 0, len(s)
        while i < n:
            c = s[i]
            if c.isdigit():
                num = 0
                while i < n and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                result += sign * num
                continue
            if c == '+':
                sign = 1
            elif c == '-':
                sign = -1
            elif c == '(':
                st.append((result, sign))
                result = 0
                sign = 1
            elif c == ')':
                saved_res, saved_sign = st.pop()
                result = saved_res + saved_sign * result
            i += 1
        return result

var calculate = function(s) {
    const st = [];
    let result = 0;
    let sign = 1;
    let i = 0;
    const n = s.length;
    while (i < n) {
        const c = s[i];
        if (c >= '0' && c <= '9') {
            let num = 0;
            while (i < n && s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s.charCodeAt(i) - 48);
                i++;
            }
            result += sign * num;
            continue;
        }
        if (c === '+') sign = 1;
        else if (c === '-') sign = -1;
        else if (c === '(') {
            st.push([result, sign]);
            result = 0;
            sign = 1;
        } else if (c === ')') {
            const [savedRes, savedSign] = st.pop();
            result = savedRes + savedSign * result;
        }
        i++;
    }
    return result;
};

class Solution {
    public int calculate(String s) {
        Deque<int[]> st = new ArrayDeque<>();
        long result = 0;
        int sign = 1;
        int i = 0, n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                long num = 0;
                while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                result += sign * num;
                continue;
            }
            if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') {
                st.push(new int[]{(int) result, sign});
                result = 0;
                sign = 1;
            } else if (c == ')') {
                int[] top = st.pop();
                result = top[0] + (long) top[1] * result;
            }
            i++;
        }
        return (int) result;
    }
}

function calculate(s: string): number {
    const st: [number, number][] = [];
    let result = 0;
    let sign = 1;
    let i = 0;
    const n = s.length;
    while (i < n) {
        const c = s[i];
        if (c >= '0' && c <= '9') {
            let num = 0;
            while (i < n && s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s.charCodeAt(i) - 48);
                i++;
            }
            result += sign * num;
            continue;
        }
        if (c === '+') sign = 1;
        else if (c === '-') sign = -1;
        else if (c === '(') {
            st.push([result, sign]);
            result = 0;
            sign = 1;
        } else if (c === ')') {
            const [savedRes, savedSign] = st.pop()!;
            result = savedRes + savedSign * result;
        }
        i++;
    }
    return result;
}

Editorial#

The stack stores the outer context that should be combined with the inner sub-expression’s result. Because there’s no * or /, sign tracking suffices — we always know whether the next number adds or subtracts. Numbers can be multi-digit, so we accumulate inside the digit loop.

Complexity#

Time: O(n).
Space: O(n) for stack depth.

Concept revision#

Decode String