Expression Calculator

Start from brute force

The obvious approach rewrites the string until one number is left. Find an innermost pair of parentheses, evaluate what is inside with two flat left-to-right passes (every * and / first, then every + and -), splice the result back in place of the group, and repeat. It works because an innermost group contains no other group, so precedence only has to be handled in flat text. But every splice rebuilds an O(n) string and there can be O(n) of them, so it costs O(n²) time and O(n) space. It is also fragile: (2-5)*2 splices to -3*2 and 7/2 to 3.5, text that a scanner built for non-negative integers cannot read.

The approach

Recursive descent writes the grammar as one function per precedence level, so precedence comes from call depth instead of rules you must remember. expression handles + and - between terms, term handles * and / between factors, and factor is a number or a parenthesized expression. Because term runs to completion before expression looks at the next operator, 3*4 is already 12 when the + applies.

The reference solution strips spaces into s and shares one cursor, pos, between the nested functions through nonlocal; peek() returns the current character, or "" at the end. number() consumes a run of digits. factor() either reads a number or consumes (, calls expression() and consumes ). term() and expression() each read one operand, then loop while peek() shows one of their operators, folding each new operand into val. Folding in a loop is what makes 10-3-2 mean (10-3)-2. The invariant: when a function returns, pos sits just past everything it parsed.

Walk through an example

Trace the first example, calc("2+3*4"), where pos is the cursor after each step.

Complexity

Optimal: O(n) time, because every character is consumed exactly once, by number() or by the step over an operator or parenthesis, and each call does constant work beyond that; O(n) space for s plus an O(d) call stack for nesting depth d. Brute force (string rewriting): O(n²) time, O(n) space.

Edge cases to test

• "10-3-2" → 5. Left associativity comes from the loop; a right-recursive rule such as expr = term "-" expr computes 10-(3-2) = 9.
• "7/2" → 3.5, and "10/2-3" → 2.0 in Python (a float equal to 2) but 2 in TypeScript. / is real division, not integer division.
• "1/0": Python raises ZeroDivisionError, while the TypeScript reference returns Infinity. Pick one behavior and make both languages agree.
• Deep nesting: each ( costs three Python frames (expression, term, factor), so roughly 330 levels of parentheses exceed the default recursion limit of 1000 and raise RecursionError.
• Unconsumed input: "2)3" → 2, and a tab before the + in 1 + 2 gives 1, because only spaces are stripped and a tab is not an operator. The reference never checks pos == len(s) at the end; a production parser should raise there.
• Unary minus is out of scope: "-3" raises ValueError in Python (from int("")) and returns NaN in TypeScript. Supporting it takes one rule: factor = "-" factor | number | "(" expr ")".

Common mistakes

• Ignoring precedence — evaluating 2 + 3 * 4 left to right gives 20 instead of 14.
• Mishandling parentheses (unbalanced, or not resolving the inner expression first).
• Forgetting multi-digit numbers or unary minus while tokenizing.
• Writing the grammar right-recursively, expr = term "-" expr, which makes subtraction and division right-associative: 10-3-2 becomes 9 and 8/4/2 becomes 4.

Follow-ups an interviewer asks next

How would you add exponentiation?

Add a level between term and factor: power = factor ("^" power)?. Use recursion on the right instead of a loop, because exponentiation is right-associative: 2^3^2 is 2^9 = 512, not 8^2 = 64. If you also add unary minus, put it outside power so that -2^2 is -4, as in standard notation.

How would you support variables and function calls, like a spreadsheet?

Extend factor: an identifier followed by ( is a call with comma-separated expression arguments, and a bare identifier is a lookup in an environment dictionary. If the same formula is evaluated many times with different inputs, parse it once into a tree and evaluate the tree, rather than re-parsing the string on every recalculation.

Can you do it without recursion?

Yes: the shunting-yard algorithm, or a two-stack evaluator, keeps a value stack and an operator stack and applies a pending operator whenever one of lower or equal precedence arrives. It is iterative and O(n), so deep nesting cannot overflow the call stack. Precedence climbing, also called Pratt parsing, is the middle ground: one recursive function driven by a table of binding powers.

How would you report syntax errors?

Check every assumption the reference makes silently. In factor, raise if the character after the inner expression is not ) and if number() consumed no digits; after the top-level expression(), raise if pos has not reached the end. Include pos in the message, as in “expected ) at column 7”.

Where this shows up

This is a tiny parser-evaluator, and the same precedence-and-stack machinery scales up to real language interpreters, spreadsheet formula engines, database query parsers, and config expression languages. Getting precedence right by hand is the transferable skill. Recursive descent is not only a teaching device: Clang’s C and C++ parser is hand-written recursive descent, because it makes precise error messages straightforward.

Reference solution

def calc(expr):
    s = expr.replace(" ", "")
    pos = 0

    def peek():
        return s[pos] if pos < len(s) else ""

    def number():
        nonlocal pos
        start = pos
        while pos < len(s) and s[pos].isdigit():
            pos += 1
        return int(s[start:pos])

    def factor():
        nonlocal pos
        if peek() == "(":
            pos += 1                 # consume "("
            val = expression()
            pos += 1                 # consume ")"
            return val
        return number()

    def term():
        nonlocal pos
        val = factor()
        while peek() in ("*", "/"):
            op = s[pos]; pos += 1
            rhs = factor()
            val = val * rhs if op == "*" else val / rhs
        return val

    def expression():
        nonlocal pos
        val = term()
        while peek() in ("+", "-"):
            op = s[pos]; pos += 1
            rhs = term()
            val = val + rhs if op == "+" else val - rhs
        return val

    return expression()


print(calc("2+3*4"))          # -> 14
print(calc("(2+3)*4"))        # -> 20
print(calc("2*(3+(4-1))"))    # -> 12

function calc(expr: string): number {
  const s = expr.replace(/ /g, "");
  let pos = 0;
  const peek = () => (pos < s.length ? s[pos] : "");

  function number(): number {
    const start = pos;
    while (pos < s.length && s[pos] >= "0" && s[pos] <= "9") pos++;
    return parseInt(s.slice(start, pos), 10);
  }
  function factor(): number {
    if (peek() === "(") {
      pos++;                 // consume "("
      const val = expression();
      pos++;                 // consume ")"
      return val;
    }
    return number();
  }
  function term(): number {
    let val = factor();
    while (peek() === "*" || peek() === "/") {
      const op = s[pos++];
      const rhs = factor();
      val = op === "*" ? val * rhs : val / rhs;
    }
    return val;
  }
  function expression(): number {
    let val = term();
    while (peek() === "+" || peek() === "-") {
      const op = s[pos++];
      const rhs = term();
      val = op === "+" ? val + rhs : val - rhs;
    }
    return val;
  }
  return expression();
}

console.log(calc("2+3*4"));       // -> 14
console.log(calc("(2+3)*4"));     // -> 20
console.log(calc("2*(3+(4-1))")); // -> 12