Basic Calculator — Stack-Based Expression Parsing with Parentheses

Problem Statement#

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

The expression can contain:

• Non-negative integers
• +, - operators
• ( and ) for grouping
• Whitespace

You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists of digits, '+', '-', '(', ')', and ' '.
• s represents a valid expression.
• '+' is not used as a unary operator.
• '-' may be used as a unary operator.
• Integer values fit in a 32-bit signed integer.

Input:  s = "1 + 1"
Output: 2

Input:  s = " 2-1 + 2 "
Output: 3

Input:  s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Why This Problem Matters#

LeetCode 224 Basic Calculator is the textbook FAANG parsing problem and shows up at Google, Meta, Amazon, and Bloomberg. It is the smallest example that captures the four-way interaction of operators, operands, parentheses, and whitespace. If you can solve this cleanly in one pass, you have the foundation for full expression-evaluator interpreters used in spreadsheets, formula engines, and SQL parsers.

The interview signal is high because there are many incorrect approaches (recursive descent without a clear grammar, two-stack shunting yard with wrong precedence, eager evaluation that mishandles signs). The cleanest solution uses a single stack to remember the sign and accumulator at each parenthesis level — a pattern recruiters specifically watch for.

The Core Insight#

We scan left to right keeping two pieces of state: result (running sum at the current level) and sign (the sign of the next number, plus 1 or minus 1). Every digit accumulates into a number; when we hit an operator or close-paren, we add sign times number to result.

Parentheses introduce nested levels. When we see an open-paren, we push the current (result, sign) onto a stack and reset result to 0 and sign to plus 1. When we see a close-paren, we finalize the current number into result, then pop (prevResult, prevSign) and set result equal to prevResult plus prevSign times result.

This single-stack approach handles arbitrary nesting depth in O(n) time and avoids any recursion (which can blow the stack on inputs with thousands of nested parens).

Visual Dry Run#

s equals "(1+(4+5+2)-3)+(6+8)".

Initial state: result = 0, sign = +1, number = 0, stack = [].

Final result equals 23. Matches expected.

Solution (Optimal)#

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    number = 0
 
    for ch in s:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == '+':
            result += sign * number
            number = 0
            sign = 1
        elif ch == '-':
            result += sign * number
            number = 0
            sign = -1
        elif ch == '(':  # save context, start fresh
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif ch == ')':
            result += sign * number
            number = 0
            prev_sign = stack.pop()
            prev_result = stack.pop()
            result = prev_result + prev_sign * result
        # whitespace ignored
 
    return result + sign * number

function calculate(s) {
  const stack = [];
  let result = 0;
  let sign = 1;
  let number = 0;
 
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      number = number * 10 + (ch.charCodeAt(0) - 48);
    } else if (ch === '+') {
      result += sign * number;
      number = 0;
      sign = 1;
    } else if (ch === '-') {
      result += sign * number;
      number = 0;
      sign = -1;
    } else if (ch === '(') {
      stack.push(result);
      stack.push(sign);
      result = 0;
      sign = 1;
    } else if (ch === ')') {
      result += sign * number;
      number = 0;
      const prevSign = stack.pop();
      const prevResult = stack.pop();
      result = prevResult + prevSign * result;
    }
  }
  return result + sign * number;
}

Complexity. Time O(n) — each character is processed once. Space O(d) where d is maximum nesting depth.

Common Mistakes#

• Forgetting to flush the final number after the loop. The trailing number is only added when an operator or close-paren forces a flush; without a final result + sign * number, the last number is dropped.
• Using recursive descent and blowing the stack on deeply nested inputs. The iterative single-stack approach handles any depth.
• Pushing only the prevResult and not the prevSign. Both are needed to combine the sub-expression result correctly.
• Treating multi-digit numbers as single characters. Always accumulate digits with number = number * 10 + digit.
• Mishandling whitespace. The cleanest approach is to ignore unknown characters in the loop.

Interview Tips#

• Sketch the grammar in BNF on the whiteboard: expression equals term ((plus or minus) term) star; term equals number or paren expression paren.
• Walk through a small nested example and explicitly call out the (result, sign) push and pop at parentheses.
• Mention that this is iterative, not recursive — important for adversarial inputs with deep nesting.
• Note that LeetCode 227 (Basic Calculator II) adds multiplication and division, and LeetCode 772 (Basic Calculator III) combines both. The single-stack pattern extends to both.
• Reject eval-based shortcuts immediately. Interviewers will fail you for using language built-ins.

Follow-up Questions#

1. What if multiplication and division are added? Use a stack of intermediate sums; multiply or divide eagerly with the previous number.
2. What if unary plus is allowed? Handle plus-after-paren or plus-at-start as an explicit unary; same stack approach works.
3. What about variables and assignment (let x equals 5)? Maintain a symbol table and treat identifiers as deferred numbers.
4. What if numbers can be floats or fractions? Replace integer accumulation with a parser that recognizes decimal points.
5. How would you support arbitrary operators with precedence? Implement the shunting-yard algorithm with operator precedence and associativity tables.

Key Takeaways#

• Single stack with (result, sign) frames handles arbitrary nesting in O(n).
• Track running result, current sign, and accumulating number as scan state.
• Flush the number into result on every operator and on close-paren.
• After the loop, do not forget the final flush — a common one-liner bug.
• The pattern extends cleanly to multiplication, division, and full expression languages.
• Avoid recursion to handle pathological deeply-nested inputs without stack overflow.