# LeetCode 736: Parse Lisp Expression ## Problem Restatement We are given a string `expression` that represents a Lisp-like expression. We need to evaluate it and return its integer value. An expression can be one of these forms: | Form | Meaning | |---|---| | Integer | A positive or negative integer | | Variable | A name whose value comes from a surrounding `let` | | `add` | Adds two expressions | | `mult` | Multiplies two expressions | | `let` | Assigns variables, then evaluates a final expression | The official syntax includes integer expressions, assigned variables, `let`, `add`, and `mult`. A `let` assigns variables sequentially, and each expression evaluates to one integer. ## Input and Output | Item | Meaning | |---|---| | Input | A valid Lisp-like expression string | | Output | The integer value of the expression | | Operators | `let`, `add`, `mult` | | Scope | Inner variable bindings override outer bindings | | Validity | The input expression is guaranteed valid | Example function shape: ```python def evaluate(expression: str) -> int: ... ``` ## Examples ### Example 1 ```python expression = "(add 1 2)" ``` This evaluates: ```text 1 + 2 = 3 ``` The answer is: ```python 3 ``` ### Example 2 ```python expression = "(mult 3 (add 2 3))" ``` First evaluate the nested expression: ```text (add 2 3) = 5 ``` Then multiply: ```text 3 * 5 = 15 ``` The answer is: ```python 15 ``` ### Example 3 ```python expression = "(let x 2 (mult x 5))" ``` The `let` expression assigns: ```text x = 2 ``` Then it evaluates: ```text (mult x 5) ``` So the answer is: ```python 10 ``` ### Example 4 ```python expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" ``` The outer `x` is `2`. Inside the nested `let`, `x` becomes `3` and `y` becomes `4`. So: ```text (add x y) = 3 + 4 = 7 ``` Then the outer multiplication uses the outer `x`: ```text 2 * 7 = 14 ``` The answer is: ```python 14 ``` ## First Thought: Split by Spaces For simple expressions like: ```python "(add 1 2)" ``` we can remove the outer parentheses and split by spaces. But this fails for nested expressions: ```python "(mult 3 (add 2 3))" ``` A plain split gives pieces that break the nested expression apart. We need to split only on spaces that are at the current parenthesis depth. That means parsing must track parentheses. ## Key Insight This problem is a small interpreter. The expression is recursive: - An `add` contains two expressions. - A `mult` contains two expressions. - A `let` contains variable assignments and a final expression. - Each nested expression can contain more nested expressions. So we write a recursive evaluator. The evaluator receives: ```python expr scope ``` `scope` maps variable names to integer values. When evaluating a nested expression, we copy the current scope so inner bindings do not leak outward. ## Algorithm Define: ```python eval_expr(expr, scope) ``` It returns the integer value of `expr`. ### Case 1: Integer If `expr` starts with a digit or `-`, return `int(expr)`. ### Case 2: Variable If `expr` does not start with `(` and is not an integer, return: ```python scope[expr] ``` ### Case 3: Parenthesized Expression Remove the outer parentheses. Then split the inside into top-level tokens. The first token is the operator. For `add`: 1. Evaluate the two arguments. 2. Return their sum. For `mult`: 1. Evaluate the two arguments. 2. Return their product. For `let`: 1. Copy the scope. 2. Process pairs of variable and expression. 3. Assign each variable sequentially. 4. Evaluate and return the final expression. ## Correctness The evaluator follows the grammar of the expression. If the expression is an integer, returning its integer value is correct. If the expression is a variable, returning the nearest value from the current scope is correct because each recursive call receives the scope visible at that point. For `add`, the expression value is defined as the sum of its two evaluated subexpressions. The algorithm recursively evaluates both arguments and returns their sum. For `mult`, the expression value is defined as the product of its two evaluated subexpressions. The algorithm recursively evaluates both arguments and returns their product. For `let`, assignments are evaluated from left to right. The algorithm processes variable-expression pairs in order and updates the local scope after each assignment. Therefore later assignments and the final expression can use earlier assignments from the same `let`. Because each `let` copies the incoming scope, inner variables override outer variables only inside that expression. When the recursive call returns, outer scopes remain unchanged. Thus the algorithm evaluates every expression according to the required scoping and operator rules. ## Complexity Let `n = len(expression)`. | Metric | Value | Why | |---|---:|---| | Time | `O(n^2)` | Substrings and token splitting can rescan nested text | | Space | `O(n^2)` | Scope copies and recursive substrings can accumulate | A lower-level index parser can reduce copying, but the recursive token solution is simpler and clear. ## Implementation ```python class Solution: def evaluate(self, expression: str) -> int: def split_top_level(s: str) -> list[str]: tokens = [] depth = 0 start = 0 for i, ch in enumerate(s): if ch == "(": depth += 1 elif ch == ")": depth -= 1 elif ch == " " and depth == 0: tokens.append(s[start:i]) start = i + 1 tokens.append(s[start:]) return tokens def eval_expr(expr: str, scope: dict[str, int]) -> int: if expr[0] == "-" or expr[0].isdigit(): return int(expr) if expr[0] != "(": return scope[expr] inner = expr[1:-1] tokens = split_top_level(inner) op = tokens[0] if op == "add": return ( eval_expr(tokens[1], scope) + eval_expr(tokens[2], scope) ) if op == "mult": return ( eval_expr(tokens[1], scope) * eval_expr(tokens[2], scope) ) local_scope = scope.copy() i = 1 while i < len(tokens) - 1: name = tokens[i] value = eval_expr(tokens[i + 1], local_scope) local_scope[name] = value i += 2 return eval_expr(tokens[-1], local_scope) return eval_expr(expression, {}) ``` ## Code Explanation The helper `split_top_level` splits only on spaces outside nested parentheses: ```python if ch == " " and depth == 0: ``` The `depth` variable increases after `(` and decreases after `)`. So this expression: ```python "mult 3 (add 2 3)" ``` splits into: ```python ["mult", "3", "(add 2 3)"] ``` The evaluator first handles atoms: ```python if expr[0] == "-" or expr[0].isdigit(): return int(expr) if expr[0] != "(": return scope[expr] ``` Integers are parsed directly. Variables are looked up in the current scope. For compound expressions, we remove the outer parentheses: ```python inner = expr[1:-1] ``` Then we split and inspect the operator: ```python tokens = split_top_level(inner) op = tokens[0] ``` For `add` and `mult`, we recursively evaluate both arguments. For `let`, we copy the scope: ```python local_scope = scope.copy() ``` Then we process assignment pairs until the last token: ```python while i < len(tokens) - 1: ``` The final token is the return expression for the `let`: ```python return eval_expr(tokens[-1], local_scope) ``` ## Testing ```python def run_tests(): s = Solution() assert s.evaluate("(add 1 2)") == 3 assert s.evaluate("(mult 3 (add 2 3))") == 15 assert s.evaluate("(let x 2 (mult x 5))") == 10 assert s.evaluate( "(let x 2 (mult x (let x 3 y 4 (add x y))))" ) == 14 assert s.evaluate("(let x 3 x 2 x)") == 2 assert s.evaluate("(let x 1 y 2 x (add x y) (add x y))") == 5 assert s.evaluate("(let x -2 y 3 (mult x y))") == -6 assert s.evaluate("(add -1 (mult 2 3))") == 5 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `"(add 1 2)"` | Basic addition | | `"(mult 3 (add 2 3))"` | Nested expression | | `"(let x 2 (mult x 5))"` | Simple variable binding | | Nested `let` with shadowing | Checks lexical scope | | Reassigning same variable | Later binding overrides earlier binding | | Sequential `let` assignments | Later values can use earlier assignments | | Negative values | Checks integer parsing | | Mixed add and mult | Checks recursive evaluation |