Parse and evaluate nested expressions with validation
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Design and implement a parser/evaluator for a parenthesized expression language where the input string may be invalid. The language uses spaces as token separators and parentheses for grouping. Supported operators: sum, prod, set. Semantics: (sum e1 e2 ... ek) returns the sum of k>=2 subexpressions; (prod e1 e2 ... ek) returns the product of k>=2 subexpressions; (set x v body) binds variable x to the value of expression v within body and any nested scopes (lexical scoping, inner bindings shadow outer ones). Tokens: integer = optional leading '-' followed by digits; variable = lowercase letter followed by zero or more lowercase letters or digits. Implement a function evaluate(expr: string) -> int that computes the value if the expression is valid; otherwise it must report an error (e.g., throw/return InvalidExpression). The evaluator must: handle arbitrary nesting and extra spaces; support negative integers; maintain proper lexical scoping; and detect errors including mismatched or missing parentheses, unknown operators, wrong arity (e.g., set must have exactly 3 arguments with the first being a variable), undefined variable references, malformed numbers, empty expressions, and 32-bit signed integer overflow. Constraints: length(expr) <= 1e5, maximum nesting depth <= 1e4. Provide and explain two approaches (recursive descent vs. iterative stack-based) and analyze time/space complexity in terms of n = length(expr). Follow-ups: extend set to support multiple bindings like (set x 1 y 2 body); add a division operator with integer truncation and division-by-zero handling.
Quick Answer: This question evaluates a developer's ability to design and implement a robust parser and evaluator for a parenthesized expression language, testing parsing, lexical scoping and variable binding, operator semantics, error detection, and safe integer arithmetic.
Implement `evaluate(expr)` for a parenthesized expression language. Spaces separate tokens and parentheses group subexpressions.
Operators:
- `(sum e1 e2 ... ek)` returns the sum of k >= 2 subexpressions.
- `(prod e1 e2 ... ek)` returns the product of k >= 2 subexpressions.
- `(set x v body)` binds variable `x` to the value of expression `v` within `body` and any nested scopes (lexical scoping; inner bindings shadow outer ones). `set` takes exactly 3 arguments and the first must be a variable.
Tokens:
- integer = optional leading `-` followed by one or more digits.
- variable = a lowercase letter followed by zero or more lowercase letters or digits.
Return the integer value when `expr` is valid. When `expr` is invalid, signal an error — in this harness, return the sentinel string `"InvalidExpression"`.
The evaluator must handle arbitrary nesting and extra spaces, support negative integers, maintain proper lexical scoping, and detect: mismatched or missing parentheses, unknown operators, wrong arity, undefined variable references, malformed numbers, empty expressions, and 32-bit signed integer overflow (any intermediate or final value outside [-2^31, 2^31-1] is invalid).
Constraints: length(expr) <= 1e5, maximum nesting depth <= 1e4.
Constraints
- length(expr) <= 1e5
- maximum nesting depth <= 1e4
- integer = optional leading '-' then one or more digits
- variable = lowercase letter then zero or more lowercase letters/digits
- sum/prod require k >= 2 subexpressions; set requires exactly 3 args with a variable first
- all intermediate and final values must fit in a 32-bit signed integer; otherwise InvalidExpression
Examples
Input: ("(sum 1 2)",)
Expected Output: 3
Explanation: 1 + 2 = 3.
Input: ("(prod 2 3 4)",)
Expected Output: 24
Explanation: 2 * 3 * 4 = 24; prod accepts more than two args.
Hints
- Tokenize first: emit '(' and ')' as standalone tokens and collapse runs of non-space, non-paren characters into atom tokens. This makes extra/leading/trailing spaces trivial to handle.
- Use recursive descent: parse() reads one expression (atom or compound); parse_compound() reads the operator then dispatches. Validate arity inside each operator branch and require the closing ')'.
- For scoping, pass an immutable copy (or a parent-linked chain) into the body of set so inner bindings shadow outer ones without mutating the caller's scope.
- Guard every add/multiply/literal with a 32-bit range check, and after the top-level parse confirm all tokens were consumed (a trailing token like an unmatched ')' means invalid).