Parse Lisp Expression - Leetcode Solution

The "Parse Lisp Expression" problem on LeetCode (https://leetcode.com/problems/parse-lisp-expression/) requires you to implement a Lisp interpreter that can evaluate expressions in a simplified version of the Lisp language.

The problem statement provides various examples of Lisp expressions that need to be evaluated, such as:

(add 1 2)
(mult 3 (add 2 3))
(let x 2 (mult x 5))

Your task is to implement a function evaluate that takes a string parameter expression representing a Lisp expression and returns its evaluation. You should assume that the input expression is well-formed.

To solve this problem, you can use recursion to evaluate the different types of expressions in the Lisp language. There are three types of Lisp expressions:

1. Integer: an integer constant, such as "123"
2. Symbol: a variable or operator, such as "add", "mult", or "x"
3. List: a parenthesized expression that contains one or more sub-expressions

Here's a step-by-step approach to solving the problem:

1. Define a function parse that takes a string representing a Lisp expression and returns a list of tokens. To do this, you can use regular expressions to split the input string into separate tokens. Here's an example implementation:

import re

def parse(expression: str) -> List[str]:
    tokens = []
    for token in re.findall(r'\(|\)|[^\s()]+', expression):
        tokens.append(token)
    return tokens

This function uses the regular expression r'\(|\)|[^\s()]+' to split the input string into separate tokens, treating parentheses as separate tokens. For example, the expression "(add 1 2)" would be parsed into the list ["(", "add", "1", "2", ")"].

2. Define a function evaluate that takes a list of tokens representing a Lisp expression and returns its evaluation. To do this, you can use recursion to evaluate the different types of expressions. Here's an example implementation:

def evaluate(tokens: List[str], env: Dict[str, int] = None) -> int:
    if not tokens:
        return 0
    if env is None:
        env = {}
    token = tokens.pop(0)
    if token == '(':
        if tokens[0] == 'add':
            tokens.pop(0)
            arg1 = evaluate(tokens, env)
            arg2 = evaluate(tokens, env)
            return arg1 + arg2
        elif tokens[0] == 'mult':
            tokens.pop(0)
            arg1 = evaluate(tokens, env)
            arg2 = evaluate(tokens, env)
            return arg1 * arg2
        elif tokens[0] == 'let':
            tokens.pop(0)
            new_env = env.copy()
            while tokens[0] != ')':
                var = tokens.pop(0)
                if tokens[0] == '(':
                    new_env[var] = evaluate(tokens, new_env)
                else:
                    new_env[var] = int(tokens.pop(0))
            tokens.pop(0) # pop final closing bracket
            return evaluate(tokens, new_env)
    else:
        if token in env:
            return env[token]
        return int(token)

This function takes a list of tokens that represent a Lisp expression, as well as an optional environment dictionary that contains the current variable bindings. It returns an integer that represents the evaluation of the input expression.

The function begins by popping the first token from the token list and determining its type. If the token is an opening parenthesis, then it recursively evaluates the sub-expressions within the parentheses. If the sub-expression is a built-in function (i.e., "add" or "mult"), then it evaluates the arguments and applies the function. If the sub-expression is a "let" expression, then it creates a new environment dictionary with the variable bindings specified in the expression, and recursively evaluates the remaining expression with the new environment.

If the token is not an opening parenthesis, then it checks if it is a variable in the current environment dictionary. If it is, then it returns the value associated with the variable. Otherwise, it assumes that the token is an integer constant and returns its value.

3. Define the main function parse_lisp_expression that takes a string parameter expression and returns its evaluation. Here's an example implementation:

from typing import List, Dict

def parse_lisp_expression(expression: str) -> int:
    tokens = parse(expression)
    return evaluate(tokens)

This function simply parses the input string into a list of tokens and then evaluates it using the evaluate function.

4. Test your implementation using the examples provided in the problem statement. For example:

assert parse_lisp_expression("(add 1 2)") == 3
assert parse_lisp_expression("(mult 3 (add 2 3))") == 15
assert parse_lisp_expression("(let x 2 (mult x 5))") == 10
assert parse_lisp_expression("(let x 2 (mult x (let x 3 y 4 (add x y))))") == 14
assert parse_lisp_expression("(let x 1 y 2 x (add x y) (add x y))") == 5

Overall, the Parse Lisp Expression problem on LeetCode requires you to implement a Lisp interpreter that can evaluate expressions in a simplified version of the Lisp language. You can solve this problem by using recursion to evaluate the different types of Lisp expressions: integers, symbols, and lists. The parse function tokenizes the input string, and the evaluate function recursively evaluates the tokens using the current environment dictionary. With these functions, you can implement the parse_lisp_expression function that parses and evaluates the input expression, and then test your implementation using the examples provided.

1