Basic Calculator

You are given a string s holding a valid arithmetic expression. It may contain non-negative integers, the operators '+' and '-', parentheses '(' and ')', and spaces. Evaluate it and return the integer result.

Minus may also be used as a negation: at the very start of the expression or right after an opening parenthesis, as in "-4 + 1" or "2 - (-3)". Plus is only ever used between two operands. Spaces can appear anywhere between tokens and carry no meaning.

Do not use any built-in that evaluates strings as code (such as eval).

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 3 · 105
• s contains only digits, '+', '-', '(', ')' and ' ', and is a valid expression.
• '-' may be unary; '+' is never unary. No two operators are adjacent (ignoring spaces).
• Every number, every intermediate value and the result fit in a signed 32-bit integer.

Pattern Path · Stacks · problem 49 of 169

Start simple

Repeatedly find an innermost pair of parentheses, evaluate it, and splice the result back into the string: O(n²) time in the worst case because of the repeated rebuilding.

The key idea

With only + and -, the expression is just a sum of numbers, each multiplied by +1 or -1. Parentheses only change those signs: a - in front of a group flips the sign of everything inside it.

So scan the string once and keep:

• result: the running sum at the current parenthesis level,
• sign: the sign that applies to the next number, and num: the digits read so far.

Digits extend num. On + or -, add sign * num to result and set the new sign. On (, push the current result and sign on a stack and start a fresh level with result = 0, sign = 1. On ), finish the inner sum, then pop the outer state and combine: result = outerResult + outerSign * result. Spaces are skipped.

Unary minus needs no special case: at the start of a level num is 0, so - simply adds 0 and sets the sign to -1. The explicit stack also means deeply nested input cannot overflow the call stack.

Complexity

• Time: O(n)
• Space: O(n) for the stack in the worst case (deep nesting)

Python

class Solution:
    def calculate(self, s: str) -> int:
        result = 0     # running sum at the current parenthesis level
        sign = 1       # sign of the number being read
        num = 0        # digits read so far
        stack = []     # (result, sign) saved for each enclosing level
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in "+-":
                result += sign * num
                num = 0
                sign = 1 if ch == "+" else -1
            elif ch == "(":
                stack.append((result, sign))
                result, sign = 0, 1
            elif ch == ")":
                result += sign * num
                num = 0
                outer_result, outer_sign = stack.pop()
                result = outer_result + outer_sign * result
        return result + sign * num

JavaScript

var calculate = function(s) {
  let result = 0;    // running sum at the current parenthesis level
  let sign = 1;      // sign of the number being read
  let num = 0;       // digits read so far
  const stack = [];  // [result, sign] saved for each enclosing level
  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + Number(ch);
    } else if (ch === "+" || ch === "-") {
      result += sign * num;
      num = 0;
      sign = ch === "+" ? 1 : -1;
    } else if (ch === "(") {
      stack.push([result, sign]);
      result = 0;
      sign = 1;
    } else if (ch === ")") {
      result += sign * num;
      num = 0;
      const [outerResult, outerSign] = stack.pop();
      result = outerResult + outerSign * result;
    }
  }
  return result + sign * num;
};

What the interviewer is checking

The interviewer is checking that you can write a careful single-pass parser: multi-digit numbers, signs, unary minus and nesting, with state saved on a stack rather than tangled special cases.

Mistakes to avoid

• Reading only one digit per number instead of accumulating num * 10 + digit.
• Forgetting to add the final pending number after the loop ends.
• Applying the minus before a group to only the first number inside it.
• Recursing once per parenthesis on deeply nested input and overflowing the call stack.

Follow-ups to expect

• Add * and / with normal precedence. (Defer the last term until the next operator.)
• Support variables or functions. (Tokenizer plus recursive descent parser.)
• Convert the expression to postfix first. (Shunting-yard algorithm.)

In real software

Spreadsheet formulas, configuration files with arithmetic, and query languages all start with a small expression evaluator like this before growing into a full parser.

Practice next