Basic Calculator with Brackets: One Pass and a Stack

You're given a string s holding a valid expression made of non-negative integers, the operators + and -, brackets and spaces. A minus sign can also be unary, but only at the very start of the expression or immediately after an opening bracket (for example -(2 + 3) or 1 - (-2)). Return the value of the expression without using any built-in function that evaluates strings.

The answer and every intermediate value fit in a 32-bit signed integer.

Examples

Input	Output	Why
`s = "1 + 1"`	`2`	The simplest case, with no brackets at all.
`s = "(1+(4+5+2)-3)+(6+8)"`	`23`	The first bracket is 9 and the second is 14.
`s = "- (3 + (4 + 5))"`	`-12`	A unary minus in front of a bracket negates all of it.

Constraints

1 ≤ s.length ≤ 3 × 10⁵
s contains digits, + - ( ) and spaces
The expression is valid

Hints

Hint 1

Start without brackets, where I'd keep a running total and the sign of the next number, which is all you need for something like 2 - 1 + 2.

Hint 2

An opening bracket starts a brand new running total, but you'll need the old total and the sign in front of the bracket again once the bracket closes, so think about where to keep them.

Hint 3

If you push the total and the sign at '(' and pop them at ')', the finished bracket's value is just total = savedTotal + savedSign × bracketValue, and nested brackets work automatically because the stack remembers each level.

Where people lose marks

Adding each digit to the total separately means 12 gets treated as 1 and then 2, so you'll want to finish building the number before using it.
Forgetting to add the last number when the string ends is easy to do if you only add numbers when you meet an operator or a bracket.
At a closing bracket people sometimes pop the total and the sign in the opposite order to the one they pushed them in, which quietly gives wrong answers on nested brackets.
Treating a space as the end of a number only works if numbers never contain spaces, which they don't here, but I'd still skip spaces explicitly so the code doesn't depend on it.

Dry run on `"5 - (2 - (1 + 4))"`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 9

Step 1 / 9

saved
total5sign+
I read the number 5 and add it with sign plus, so the running total becomes 5.
Step 2 / 9

saved
5, −0
total0sign+
An opening bracket, so the total 5 and the sign minus in front of it are saved and the bracket starts again from 0.
Step 3 / 9

saved
5, −0
total2sign+
I read the number 2 and add it with sign plus, so the running total becomes 2.
Step 4 / 9

saved
5, −02, −1
total0sign+
An opening bracket, so the total 2 and the sign minus in front of it are saved and the bracket starts again from 0.
Step 5 / 9

saved
5, −02, −1
total1sign+
I read the number 1 and add it with sign plus, so the running total becomes 1.
Step 6 / 9

saved
5, −02, −1
total5sign+
I read the number 4 and add it with sign plus, so the running total becomes 5.
Step 7 / 9

saved
5, −0
total-3sign+
The bracket closes with value 5. Popping 2 and minus gives 2 − 5 = -3.
Step 8 / 9

saved
total8sign+
The bracket closes with value -3. Popping 5 and minus gives 5 − -3 = 8.
Step 9 / 9

saved
answer8
The string has ended and nothing is still saved, so the answer is 8.

How to think about it

Without brackets the problem is easy enough, because you'd keep a running total, read each number, and add it with the most recent sign (plus 1 or minus 1). A unary minus at the start is handled by the same rule, since it's simply a sign in front of the first number.

An opening bracket means you have to put that work on hold. I'd push the current total and the sign sitting in front of the bracket onto a stack, then reset total to 0 and the sign to plus, and carry on exactly as before inside the bracket. When the closing bracket arrives the bracket's value is in total, so you pop the saved sign and saved total and combine them as savedTotal + savedSign × total. Every bracket is pushed once and popped once, so as far as I can see the whole scan stays linear even when the brackets are nested quite deeply.

Multi-digit numbers are easy to get wrong. You have to keep reading digits and build the number with num = num × 10 + digit before you add it to anything.

Complexity. Time O(n) · Space O(depth of brackets)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def calculate(s):
    total, sign, stack, i = 0, 1, [], 0
    while i < len(s):
        c = s[i]
        if c.isdigit():
            num = 0
            while i < len(s) and s[i].isdigit():      # read the whole number first
                num = num * 10 + int(s[i])
                i += 1
            total += sign * num
            continue
        if c == '+':
            sign = 1
        elif c == '-':
            sign = -1
        elif c == '(':
            stack.append((total, sign))             # put the outer work on hold
            total, sign = 0, 1
        elif c == ')':
            saved_total, saved_sign = stack.pop()
            total = saved_total + saved_sign * total
        i += 1
    return total

#include <string>
#include <utility>
#include <vector>

long long solve(const std::string& s) {
    long long total = 0, sign = 1;
    std::vector<std::pair<long long, long long>> stack;
    size_t i = 0;
    while (i < s.size()) {
        char c = s[i];
        if (c >= '0' && c <= '9') {
            long long num = 0;
            while (i < s.size() && s[i] >= '0' && s[i] <= '9') num = num * 10 + (s[i++] - '0');
            total += sign * num;
            continue;
        }
        if (c == '+') sign = 1;
        else if (c == '-') sign = -1;
        else if (c == '(') { stack.push_back({total, sign}); total = 0; sign = 1; }   // outer work on hold
        else if (c == ')') { auto [t, g] = stack.back(); stack.pop_back(); total = t + g * total; }
        ++i;
    }
    return total;
}

class Solution {
    public long calculate(String s) {
        long total = 0, sign = 1;
        long[] savedTotal = new long[s.length() + 1], savedSign = new long[s.length() + 1];
        int top = 0, i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                long num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) num = num * 10 + (s.charAt(i++) - '0');
                total += sign * num;
                continue;
            }
            if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') { savedTotal[top] = total; savedSign[top++] = sign; total = 0; sign = 1; }
            else if (c == ')') { top--; total = savedTotal[top] + savedSign[top] * total; }
            i++;
        }
        return total;
    }
}

function calculate(s) {
  let total = 0, sign = 1, i = 0;
  const stack = [];
  while (i < s.length) {
    const c = s[i];
    if (c >= '0' && c <= '9') {
      let num = 0;
      while (i < s.length && s[i] >= '0' && s[i] <= '9') num = num * 10 + (s.charCodeAt(i++) - 48);
      total += sign * num;
      continue;
    }
    if (c === '+') sign = 1;
    else if (c === '-') sign = -1;
    else if (c === '(') { stack.push([total, sign]); total = 0; sign = 1; }   // put the outer work on hold
    else if (c === ')') { const [t, g] = stack.pop(); total = t + g * total; }
    i++;
  }
  return total;
}

fn solve(s: &str) -> i64 {
    let b = s.as_bytes();
    let (mut total, mut sign, mut i) = (0i64, 1i64, 0usize);
    let mut stack: Vec<(i64, i64)> = Vec::new();
    while i < b.len() {
        let c = b[i];
        if c.is_ascii_digit() {
            let mut num = 0i64;
            while i < b.len() && b[i].is_ascii_digit() {
                num = num * 10 + (b[i] - b'0') as i64;
                i += 1;
            }
            total += sign * num;
            continue;
        }
        match c {
            b'+' => sign = 1,
            b'-' => sign = -1,
            b'(' => {
                stack.push((total, sign));          // put the outer work on hold
                total = 0;
                sign = 1;
            }
            b')' => {
                let (t, g) = stack.pop().unwrap();
                total = t + g * total;
            }
            _ => {}
        }
        i += 1;
    }
    total
}

import Data.Char (isDigit, digitToInt)

-- State: running total, current sign, and a stack of (saved total, saved sign) with its top at the head.
solve :: String -> Integer
solve = go 0 1 []
  where
    go total _ _ [] = total
    go total sign st s@(c : cs)
      | isDigit c = let (ds, rest) = span isDigit s
                        num = foldl (\a d -> a * 10 + toInteger (digitToInt d)) 0 ds
                    in go (total + sign * num) sign st rest
      | c == '+' = go total 1 st cs
      | c == '-' = go total (-1) st cs
      | c == '(' = go 0 1 ((total, sign) : st) cs
      | c == ')' = case st of
          ((t, g) : rest) -> go (t + g * total) 1 rest cs
          []              -> total
      | otherwise = go total sign st cs

Variants to try

If you add multiplication and division you'll need precedence, and a common approach keeps a stack of terms where * and / combine with the top term while + and - push a new one.
The same push-at-'(' and pop-at-')' idea evaluates any expression with nested scopes, for example decoding a string such as 3[a2[c]] where each bracket repeats its contents.
You could also convert the expression to reverse Polish notation with the shunting-yard algorithm and then evaluate that, which is longer but generalises to more operators.

Next problems

Medium15 min

A calculator for plus, minus and brackets

Examples

Constraints

Hints

Where people lose marks

Dry run on `"5 - (2 - (1 + 4))"`

How to think about it

The solution, in six languages

Variants to try

Next problems

Evaluate reverse Polish notation

Balanced brackets

Days until a warmer day

Keep going

Evaluate reverse Polish notation

Balanced brackets

Days until a warmer day

The pattern behind it

A calculator for plus, minus and brackets

Examples

Constraints

Hints

Where people lose marks

Dry run on "5 - (2 - (1 + 4))"

How to think about it

The solution, in six languages

Variants to try

Next problems

Evaluate reverse Polish notation

Balanced brackets

Days until a warmer day

Keep going

Evaluate reverse Polish notation

Balanced brackets

Days until a warmer day

The pattern behind it

Dry run on `"5 - (2 - (1 + 4))"`