Quick Overview

This question evaluates the ability to parse and evaluate nested Lisp-like expressions, manage variable bindings and scope resolution, and detect malformed input and syntax errors.

Handle invalid Lisp expression parsing

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

##### Question LeetCode 736. Parse Lisp Expression – Given a string representing a Lisp-like expression containing let/add/mult operations and variable bindings, evaluate the expression and return the integer result. In addition to the standard problem, the input string may be syntactically invalid; detect invalid cases (e.g., mismatched parentheses, unknown tokens) and return an error indicator. https://leetcode.com/problems/parse-lisp-expression/description/

Quick Answer: This question evaluates the ability to parse and evaluate nested Lisp-like expressions, manage variable bindings and scope resolution, and detect malformed input and syntax errors.

You are given a string `expression` representing a Lisp-like expression. Evaluate it and return its integer result. The grammar supports three operators and integer/variable atoms: - An **integer**: an optional leading `-` followed by one or more digits (e.g. `-12`, `7`). - A **variable**: a lowercase letter followed by zero or more lowercase letters or digits (e.g. `x`, `a1`). The names `let`, `add`, `mult` are reserved and are never variable names. - `(add e1 e2)` — evaluates `e1` and `e2` and returns their sum. - `(mult e1 e2)` — evaluates `e1` and `e2` and returns their product. - `(let v1 e1 v2 e2 ... vn en expr)` — binds each variable `vi` to the value of `ei` (evaluated left to right, with earlier bindings in scope for later ones), then returns the value of the trailing `expr`. A `let` always has at least the trailing expression. Variable scoping is lexical: an inner expression sees the innermost binding of a name. **The twist (Uber variant):** the input may be syntactically or semantically invalid. If the expression is malformed — mismatched/unbalanced parentheses, an unknown operator token, a reference to a variable that is not in scope, a malformed integer, an empty string, or trailing characters after a complete expression — your function must NOT crash. Instead it must return the sentinel string `"ERROR"`. Return the integer result for valid input, or the string `"ERROR"` for any invalid input.

Constraints

  • 1 <= expression length (an empty string is treated as invalid -> 'ERROR').
  • Valid expressions follow the let/add/mult grammar described above.
  • All intermediate and final integer values for valid inputs fit in a 32-bit signed integer.
  • Invalid inputs (mismatched parentheses, unknown tokens, undefined variables, malformed integers, trailing characters) must return the string 'ERROR' rather than raising.
  • Variable names are lowercase-letter-initial; 'let', 'add', 'mult' are reserved keywords.

Examples

Input: ("(let x 2 (mult x (let x 3 y 4 (add x y))))",)

Expected Output: 14

Explanation: Outer x=2; inner let rebinds x=3, y=4, inner (add x y)=7; (mult 2 7)=14.

Input: ("(let x 3 x 2 x)",)

Expected Output: 2

Explanation: x is bound to 3, then rebound to 2; the trailing expression x evaluates to the latest binding, 2.

Hints

  1. Use a recursive-descent parser with a single moving index into the string; evaluate `(add ...)`, `(mult ...)`, and `(let ...)` by their leading operator token after consuming '('.
  2. For `let`, scan variable/value pairs left to right, layering bindings into a copy of the enclosing scope; the final token (or parenthesized sub-expression) before ')' is the result expression — distinguish it by peeking whether the next non-space char is ')'.
  3. Wrap the whole evaluation in a try/except (or explicit error path): any structural problem — missing ')', unknown operator, unbound variable, leftover characters after the top-level expression — should produce the 'ERROR' sentinel instead of crashing.

Loading coding console...