Evaluate nested add and sub expressions

The input is a tiny language with one grammar rule:

expr   := number | name "(" expr ("," expr)* ")"
name   := "add" | "sub"
number := "-"? digit+

Every function call nests its arguments, so the natural tool is a recursive
descent parser that evaluates as it parses. There is no operator precedence to
worry about (unlike Basic Calculator): the parentheses already make the tree
explicit.

Brute force first. A candidate might repeatedly find the innermost call with
a regex like (add|sub)\(-?\d+,-?\d+\), evaluate it, and splice the number back
into the string until only a number is left. It works, but each pass rescans and
rebuilds the string, so it is O(n^2) on deep nesting. Mention it, then move on.

Optimal: one pass with a cursor. Keep an index i into the string.

• parse_expr() looks at the current character. A digit or - starts a
  number. A letter starts a function name.
• For a function, read the name, expect (, then call parse_expr() for the
  first argument, and keep calling it after every , until ).
• Apply the function to the collected values and return the result.

Invariant: when parse_expr() returns, i points just past the expression it
consumed (and past trailing whitespace). Each character is read exactly once, so
the whole evaluation is linear.

add sums all its arguments (one or more). sub takes exactly two and returns
first - second. Anything else (unknown name, wrong arity, missing parenthesis,
trailing junk) raises a ValueError with the position, which interviewers like
to see.

Recursion depth equals nesting depth. If inputs can nest thousands of levels
deep, switch to the explicit-stack version in the follow-ups.

from typing import Callable


class ExpressionError(ValueError):
    pass


def _add(args: list[int]) -> int:
    return sum(args)


def _sub(args: list[int]) -> int:
    if len(args) != 2:
        raise ExpressionError(f"sub expects 2 arguments, got {len(args)}")
    return args[0] - args[1]


FUNCTIONS: dict[str, Callable[[list[int]], int]] = {"add": _add, "sub": _sub}


class Evaluator:
    def __init__(self, text: str) -> None:
        self.s = text
        self.i = 0

    def evaluate(self) -> int:
        self._skip_spaces()
        value = self._expr()
        if self.i != len(self.s):
            self._fail("unexpected trailing input")
        return value

    def _expr(self) -> int:
        if self.i >= len(self.s):
            self._fail("unexpected end of input")
        ch = self.s[self.i]
        if ch.isdigit() or ch == "-":
            return self._number()
        if ch.isalpha():
            return self._call()
        self._fail(f"unexpected character {ch!r}")

    def _number(self) -> int:
        start = self.i
        if self.s[self.i] == "-":
            self.i += 1
        digits_start = self.i
        while self.i < len(self.s) and self.s[self.i].isdigit():
            self.i += 1
        if self.i == digits_start:
            self._fail("expected digits")
        value = int(self.s[start:self.i])
        self._skip_spaces()
        return value

    def _call(self) -> int:
        start = self.i
        while self.i < len(self.s) and self.s[self.i].isalpha():
            self.i += 1
        name = self.s[start:self.i]
        fn = FUNCTIONS.get(name)
        if fn is None:
            self.i = start
            self._fail(f"unknown function {name!r}")
        self._skip_spaces()
        self._expect("(")
        args = [self._expr()]
        while self._peek() == ",":
            self.i += 1
            self._skip_spaces()
            args.append(self._expr())
        self._expect(")")
        return fn(args)

    def _peek(self) -> str:
        return self.s[self.i] if self.i < len(self.s) else ""

    def _expect(self, ch: str) -> None:
        if self._peek() != ch:
            self._fail(f"expected {ch!r}")
        self.i += 1
        self._skip_spaces()

    def _skip_spaces(self) -> None:
        while self.i < len(self.s) and self.s[self.i].isspace():
            self.i += 1

    def _fail(self, message: str) -> None:
        raise ExpressionError(f"{message} at position {self.i}")


def evaluate(expression: str) -> int:
    return Evaluator(expression).evaluate()


if __name__ == "__main__":
    assert evaluate("7") == 7
    assert evaluate("add(2,3)") == 5
    assert evaluate("sub(10,add(4,sub(9,6)))") == 3
    assert evaluate(" add( sub(0, 8) , 20 , -2 ) ") == 10
    assert evaluate("add(42)") == 42
    for bad in ["", "add(1,2", "mul(2,3)", "sub(1)", "add(1,2))", "add()"]:
        try:
            evaluate(bad)
        except ExpressionError:
            pass
        else:
            raise AssertionError(bad)
    print("ok")

• Time: O(n) for a string of length n. The cursor only moves forward and each
  character is examined a constant number of times.
• Space: O(d) for the recursion stack, where d is the nesting depth (O(n) in the
  worst case, e.g. add(add(add(...)))). Each call also holds its argument list,
  which adds O(n) in total at worst.

• "7" -> 7 (a bare number is a valid expression)
• "-15" -> -15
• "add(2,3)" -> 5
• "sub(3,10)" -> -7 (order matters: first minus second)
• "sub(10,add(4,sub(9,6)))" -> 3 (inner sub is 3, add is 7, outer is 3)
• "add(1,2,3,4)" -> 10 (variadic add)
• "add(42)" -> 42 (single-argument add)
• " add( sub(0, 8) , 20 , -2 ) " -> 10 (whitespace everywhere)
• "add(100000000000,100000000000)" -> 200000000000 (Python ints do not overflow; in
  Java or C++ discuss long)
• "" -> error, unexpected end of input
• "add(1,2" -> error, expected )
• "add(1,2))" -> error, trailing input
• "mul(2,3)" -> error, unknown function
• "sub(1)" -> error, wrong arity

1. More operators (mul, div, max, neg). Add entries to the
   FUNCTIONS table, each with its own arity check. Define integer division
   explicitly (truncate toward zero, like LeetCode 3749) and raise on division by
   zero. The parser does not change, which is the point of the dispatch table.
2. Very deep nesting (100k levels). Python's recursion limit breaks the
   recursive parser. Use an explicit stack: on name( push a frame
   (name, []); on a number append it to the top frame's list; on ) pop the
   frame, apply the function, and append the result to the new top (or keep it as
   the final answer). Same O(n) time, and the stack lives on the heap.
3. Variables, like let(x, 5, add(x, x)). This is LeetCode 736 (Parse Lisp
   Expression). Pass a chain of scopes (a list of dicts, or a dict copied per
   let) into _expr. Identifiers that are not followed by ( are variable
   lookups. Inner scopes shadow outer ones and disappear when the let returns.
4. Evaluate many times with different inputs. Split parsing from evaluation:
   build an AST (Num(v), Call(name, args)) once, then walk it. This also
   enables constant folding and caching of repeated subtrees by their text.
5. Report the error location precisely. Already raised with a position; a
   follow-up may ask for the full error message format, or to recover and
   report all errors, which needs a tokenizer and synchronization on ,/).

Mid-level (L4)

• Recognizes the recursive structure and writes a working parser for add
  and sub with two integer arguments.
• Handles multi-digit and negative numbers correctly.
• Walks through a nested example by hand and states O(n) time.

Senior (L5)

• Writes a clean single-pass cursor parser without string slicing or re-scanning,
  and explains the invariant on the cursor position.
• Handles whitespace, variadic add, and malformed input with clear errors.
• Adds mul/div through a dispatch table and states division semantics
  without being asked.

Staff (L6+)

• Separates tokenizing, parsing and evaluation, and explains when an AST pays
  off (repeated evaluation, variables, optimization).
• Calls out recursion depth as a production risk and sketches the explicit-stack
  version.
• Extends to scoped variables (let) cleanly and discusses how this grows into a
  small interpreter: grammar definition, error recovery, and testing strategy.