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:

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

Example function shape:

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

Examples

Example 1

expression = "(add 1 2)"

This evaluates:

1 + 2 = 3

The answer is:

3

Example 2

expression = "(mult 3 (add 2 3))"

First evaluate the nested expression:

(add 2 3) = 5

Then multiply:

3 * 5 = 15

The answer is:

15

Example 3

expression = "(let x 2 (mult x 5))"

The let expression assigns:

x = 2

Then it evaluates:

(mult x 5)

So the answer is:

10

Example 4

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:

(add x y) = 3 + 4 = 7

Then the outer multiplication uses the outer x:

2 * 7 = 14

The answer is:

14

First Thought: Split by Spaces

For simple expressions like:

"(add 1 2)"

we can remove the outer parentheses and split by spaces.

But this fails for nested expressions:

"(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:

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:

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:

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).

A lower-level index parser can reduce copying, but the recursive token solution is simpler and clear.

Implementation

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:

if ch == " " and depth == 0:

The depth variable increases after ( and decreases after ).

So this expression:

"mult 3 (add 2 3)"

splits into:

["mult", "3", "(add 2 3)"]

The evaluator first handles atoms:

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:

inner = expr[1:-1]

Then we split and inspect the operator:

tokens = split_top_level(inner)
op = tokens[0]

For add and mult, we recursively evaluate both arguments.

For let, we copy the scope:

local_scope = scope.copy()

Then we process assignment pairs until the last token:

while i < len(tokens) - 1:

The final token is the return expression for the let:

return eval_expr(tokens[-1], local_scope)

Testing

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()