Stack crash course ↗ · 30

224. Basic Calculator

Evaluate a string of +, -, parentheses and non-negative integers in a single left-to-right scan. A stack remembers the partial result and sign in front of each ( so nested groups fold back in correctly.

● HardStackParsingTypeScript

PROBLEM What we're solving

Given a valid expression string with +, -, parentheses, spaces and non-negative integers, return its integer value. No * or /, but a leading or unary minus like -(3+2) is allowed. Example: "(1+(4+5+2)-3)+(6+8)". The inner group (4+5+2)=11, so the first group is 1+11-3=9, and (6+8)=14, giving 9+14=23.

KEY IDEA A stack freezes the outer state at every "("

Insight → keep a running result and the sign (+1/-1) that applies to the next number. When you hit (, push the current result and the sign in front of it, then reset to evaluate the inside as a brand-new expression. When you hit ), the inner result is finished — multiply it by the saved sign and add back the saved outer result.

That turns arbitrarily nested parentheses into the same flat scan, with the stack acting as memory for "where was I before this group?".

RECIPE Scan once; commit numbers as the sign demands

1 · State. result = 0, sign = +1, num = 0, an empty stack.
2 · Digit. Extend the current number: num = num * 10 + digit. Don't commit yet — more digits may follow.
3 · + / -. Commit the pending number with result += sign * num, reset num = 0, and set sign to +1 or -1 for the next number.
4 · (. Push result then sign, then reset both — start the sub-expression fresh.
5 · ). Commit the last inner number, then result = result * stack.pop() + stack.pop() (saved sign, then saved outer total).
6 · End. Return result + sign * num to commit any trailing number.

Classic confusion → a - is a sign on the next number, not a binary subtraction you do immediately. You never "subtract"; you fold sign * num into result. This is also why multi-digit numbers must be built up (num * 10 + digit) and only committed at the next operator, paren, or end of string.

COST Complexity & alternatives

Recursive re-parse per group

O(n²)

Find each () span and re-scan it; nested groups get re-read many times.

One pass + stack

O(n)

Each char handled once; stack depth ≤ paren nesting → O(n) space.

You can solve it with explicit recursion (treat each ( as a recursive call), but the iterative stack version is the same idea with the call stack made explicit — and avoids re-scanning.

Pattern transfer → the "commit-on-operator, push state on (" scan generalizes to Basic Calculator II (add *// via a number stack), Basic Calculator III (both, with parens), Decode String (push count + built string on [), and Evaluate Reverse Polish Notation.

RUN IT Carry a running result + sign; push state on ( and restore on )

s =

step 0 / 20

STARTScan "(1+(4+5+2)-3)+(6+8)" left to right. Start with result=0, sign=+1, num=0, empty stack.

1function calculate(s: string): number {
2▶  let result = 0;        // running total of the current level
3▶  let sign = 1;          // +1 or -1 applied to the next number
4▶  let num = 0;           // the integer currently being built
5▶  const stack: number[] = []; // saved (result, sign) pairs
6 
7  for (const ch of s) {
8    if (ch >= '0' && ch <= '9') {
9      num = num * 10 + (ch.charCodeAt(0) - 48); // build multi-digit
10    } else if (ch === '+') {
11      result += sign * num;  // commit the pending number
12      num = 0;
13      sign = 1;
14    } else if (ch === '-') {
15      result += sign * num;
16      num = 0;
17      sign = -1;
18    } else if (ch === '(') {
19      stack.push(result);    // save the outer total...
20      stack.push(sign);      // ...and the sign in front of '('
21      result = 0;            // start a fresh sub-expression
22      sign = 1;
23    } else if (ch === ')') {
24      result += sign * num;          // commit last number inside ()
25      num = 0;
26      result *= stack.pop()!;        // apply the saved sign
27      result += stack.pop()!;        // add back the outer total
28    }
29    // spaces fall through and are ignored
30  }
31  return result + sign * num;        // commit any trailing number
32}

s =(011+2(344+556+728)9-10311)12+13(14615+16817)18

State

result

sign

num

(empty)

stack

cursor / sign +1number being builtresult committedstack contentssign -1

slowfast

TYPESCRIPT The solution, annotated

calculate.ts
function calculate(s: string): number {
  let result = 0;        // running total of the current level
  let sign = 1;          // +1 or -1 applied to the next number
  let num = 0;           // the integer currently being built
  const stack: number[] = []; // saved (result, sign) pairs

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch.charCodeAt(0) - 48); // build multi-digit
    } else if (ch === '+') {
      result += sign * num;  // commit the pending number
      num = 0;
      sign = 1;
    } else if (ch === '-') {
      result += sign * num;
      num = 0;
      sign = -1;
    } else if (ch === '(') {
      stack.push(result);    // save the outer total...
      stack.push(sign);      // ...and the sign in front of '('
      result = 0;            // start a fresh sub-expression
      sign = 1;
    } else if (ch === ')') {
      result += sign * num;          // commit last number inside ()
      num = 0;
      result *= stack.pop()!;        // apply the saved sign
      result += stack.pop()!;        // add back the outer total
    }
    // spaces fall through and are ignored
  }
  return result + sign * num;        // commit any trailing number
}

Reading it block by block

Lines 2–5 — state. result is the total of the current parenthesis level, sign is the +1/-1 waiting in front of the next number, num is the integer being assembled digit by digit, and stack stores (outer result, saved sign) pairs.

Lines 8–9 — build the number. On a digit we never commit immediately — we extend num = num * 10 + digit so multi-digit integers like 42 form correctly. charCodeAt(0) - 48 converts the digit char to its value.

Lines 10–18 — operators commit. A + or - means the current number is final: fold sign * num into result, reset num, and store the new sign for what comes next.

Lines 19–23 — open paren. Push result and sign to freeze the outer state, then zero both so the sub-expression starts clean.

Lines 24–28 — close paren. Commit the last inner number, then result *= stack.pop() applies the saved sign (the one in front of the () and result += stack.pop() adds back the outer total.

Line 32 — flush. The loop commits numbers only when it meets the next token, so a trailing number (no operator after it) is added once at the end: result + sign * num.

Complexity → Each character is processed exactly once with O(1) work, so O(n) time. The stack grows by two entries per (, bounded by the nesting depth, so O(n) space in the worst case.

INTERVIEWFollow-ups they'll ask

"Now support * and / too." (LC 227 / 772) Keep a stack of numbers; on *// immediately combine with the stack top so precedence is handled, then sum the stack at the end.
"Handle a unary minus like -3 or -(2+1)." Initialising num = 0 and result = 0 means a leading - already works — it just sets sign = -1 with result still 0.
"Why not recursion?" You can — each ( is a recursive call returning the inner value and the index it stopped at. The iterative stack makes the same call-stack explicit and avoids deep recursion limits.
"What if the input has spaces?" They fall through every branch and are ignored, so no special handling is needed.

OPTIMAL Stack

calculate.ts
function calculate(s: string): number {
  let result = 0;        // running total of the current level
  let sign = 1;          // +1 or -1 applied to the next number
  let num = 0;           // the integer currently being built
  const stack: number[] = []; // saved (result, sign) pairs

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch.charCodeAt(0) - 48); // build multi-digit
    } else if (ch === '+') {
      result += sign * num;  // commit the pending number
      num = 0;
      sign = 1;
    } else if (ch === '-') {
      result += sign * num;
      num = 0;
      sign = -1;
    } else if (ch === '(') {
      stack.push(result);    // save the outer total...
      stack.push(sign);      // ...and the sign in front of '('
      result = 0;            // start a fresh sub-expression
      sign = 1;
    } else if (ch === ')') {
      result += sign * num;          // commit last number inside ()
      num = 0;
      result *= stack.pop()!;        // apply the saved sign
      result += stack.pop()!;        // add back the outer total
    }
    // spaces fall through and are ignored
  }
  return result + sign * num;        // commit any trailing number
}

ALT 1 Recursive descent

O(n) time · O(n) recursion depth

Treat each ( as a recursive call that evaluates the inner expression and returns both its value and the index just past its ).

approach-2.ts
function calculate(s: string): number {
  // Evaluate s starting at index i (just after an optional '(').
  // Returns the value of this level and the index AFTER its matching ')'
  // (or s.length for the top level).
  function eval(i: number): [number, number] {
    let result = 0;   // running total of this level
    let sign = 1;     // +1 or -1 applied to the next number
    let num = 0;      // integer currently being built
    let haveNum = false;

    while (i < s.length) {
      const ch = s[i];
      if (ch >= '0' && ch <= '9') {
        num = num * 10 + (ch.charCodeAt(0) - 48); // build multi-digit
        haveNum = true;
        i++;
      } else if (ch === '+') {
        result += sign * num; // commit pending number
        num = 0;
        haveNum = false;
        sign = 1;
        i++;
      } else if (ch === '-') {
        result += sign * num;
        num = 0;
        haveNum = false;
        sign = -1;
        i++;
      } else if (ch === '(') {
        // Recurse on the sub-expression starting just after '('
        const [inner, next] = eval(i + 1);
        num = inner;       // the group's value acts like one number
        haveNum = true;
        i = next;          // jump past the matching ')'
      } else if (ch === ')') {
        // End of this level: commit and hand back the index past ')'
        if (haveNum) result += sign * num;
        return [result, i + 1];
      } else {
        i++; // skip spaces
      }
    }
    // Top level reached the end of the string
    if (haveNum) result += sign * num;
    return [result, i];
  }

  return eval(0)[0];
}

Note → The call stack replaces the explicit operand/sign stack of the optimal scan: each ( opens a frame and the matching ) returns its value plus the resume index, so the caller can continue exactly where the group ended. Clean to reason about, but a deeply nested input could overflow the recursion limit.

ALT 2 Two-stack evaluator

O(n) time · O(n) space

One stack of operands and one of operators, applying lower-precedence ops before pushing — the textbook shunting-style evaluator that extends straight to * and /.

approach-3.ts
function calculate(s: string): number {
  const nums: number[] = []; // operand stack
  const ops: string[] = [];  // operator stack ('+', '-', '(')

  // Pop the top operator and apply it to the top two operands.
  function apply(): void {
    const b = nums.pop()!;
    const a = nums.pop()!;
    const op = ops.pop()!;
    nums.push(op === '+' ? a + b : a - b);
  }

  // '+' and '-' share precedence 1; '(' is a barrier with precedence 0.
  function prec(op: string): number {
    return op === '+' || op === '-' ? 1 : 0;
  }

  let i = 0;
  let prevWasOperand = false; // distinguishes unary '-' from binary '-'

  while (i < s.length) {
    const ch = s[i];
    if (ch === ' ') {
      i++;
    } else if (ch >= '0' && ch <= '9') {
      let num = 0;
      while (i < s.length && s[i] >= '0' && s[i] <= '9') {
        num = num * 10 + (s.charCodeAt(i) - 48); // build multi-digit
        i++;
      }
      nums.push(num);
      prevWasOperand = true;
    } else if (ch === '(') {
      ops.push('(');
      prevWasOperand = false;
      i++;
    } else if (ch === ')') {
      while (ops.length > 0 && ops[ops.length - 1] !== '(') apply();
      ops.pop(); // discard the matching '('
      prevWasOperand = true;
      i++;
    } else {
      // ch is '+' or '-'
      // A '-' with no operand before it (start, after '(' or another op) is unary.
      if (ch === '-' && !prevWasOperand) {
        nums.push(0); // turn unary minus into 0 - x
      }
      while (
        ops.length > 0 &&
        ops[ops.length - 1] !== '(' &&
        prec(ops[ops.length - 1]) >= prec(ch)
      ) {
        apply(); // flush equal/higher precedence before pushing
      }
      ops.push(ch);
      prevWasOperand = false;
      i++;
    }
  }

  while (ops.length > 0) apply();
  return nums.pop()!;
}

Note → More machinery than the sign-stack scan for this exact problem, but it is the general precedence-climbing evaluator: to support * and / (Basic Calculator II / III) you only give them precedence 2 in prec and extend apply — the rest is unchanged.

MNEMONIC The one-liner

"Carry a sign, build a number, freeze the outside on ( and thaw it on )."

TRIGGERS When you see _ → reach for _

expression with + - and parentheses	running result + sign, stack on (
nested groups change scope	push (result, sign) before recursing in
multi-digit non-negative integers	num = num*10 + digit, commit later
add * and / with precedence	stack of numbers (Calculator II)

SKELETON The reusable shape

skeleton.ts
let result = 0, sign = 1, num = 0;
const stack: number[] = [];
for (const ch of s) {
  if (ch >= '0' && ch <= '9') num = num * 10 + (+ch);
  else if (ch === '+') { result += sign * num; num = 0; sign = 1; }
  else if (ch === '-') { result += sign * num; num = 0; sign = -1; }
  else if (ch === '(') { stack.push(result, sign); result = 0; sign = 1; }
  else if (ch === ')') {
    result += sign * num; num = 0;
    result = result * stack.pop()! + stack.pop()!;
  }
}
return result + sign * num;

FLASHCARDS Tap to flip

What three running scalars does the scan maintain?

result (total of this level), sign (+1/-1 for the next number), and num (the integer being built).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does "(1+(4+5+2)-3)+(6+8)" evaluate to?

QUESTION 02

When you encounter "(", what is pushed onto the stack?

QUESTION 03

Why is the number built with num = num * 10 + digit rather than committed per digit?

QUESTION 04

How is subtraction actually performed in this algorithm?

QUESTION 05

On ), which expression correctly closes the group (saved sign then saved outer result)?

QUESTION 06

What is the time and space complexity?

QUESTION 07

Why is a final "result + sign * num" needed after the loop?

QUESTION 08

#224 · Basic CalculatorEvaluate a string with +, -, parentheses and non-negative integers in one linear scan, using a stack to save the partial result and sign before each open parenthesis and restore them on the matching close.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA A stack freezes the outer state at every "("

RECIPE Scan once; commit numbers as the sign demands

COST Complexity & alternatives

RUN IT Carry a running result + sign; push state on ( and restore on )

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Stack

ALT 1 Recursive descent

ALT 2 Two-stack evaluator

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _