LeetCode Solutions Blog

Parse Lisp Expression

Number: 736

Difficulty: Hard

Paid? No

Companies: Affirm

Problem Description

Evaluate a string representing a Lisp-like expression that may include integers, variable names, and three types of expressions: let, add, and mult. The expression can contain nested scopes, and variables follow lexical scoping rules.

Key Insights

Recursively parse the expression token by token.
Use a map (or hash table) to maintain variable bindings and manage scope.
For let expressions, process variable assignments sequentially; later assignments can shadow earlier ones.
Ensure that look-up checks the innermost scope first.
Parsing requires careful handling of parentheses and white space separation.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tokens in the expression since each token is processed once. Space Complexity: O(n), due to the recursion stack and storage for variable scopes.

Solution

We solve the problem by designing a recursive parser that processes each token. The parser distinguishes between numbers, variable names, and compound expressions that start with a left parenthesis. For compound expressions:

If the expression begins with "let", we sequentially assign variables to evaluated expressions, storing these in a map for the current scope.
If the expression begins with "add" or "mult", we evaluate the two inner expressions and return their sum or product, respectively. A key trick is to maintain a scoped mapping of variable values. When entering a new let expression, we begin with the current scope and add new bindings. When the inner expression is evaluated, bindings that were added in the let block are discarded on returning to the outer scope.

Code Solutions

# Python solution with detailed comments:
class Solution:
    def evaluate(self, expression: str) -> int:
        # Split the expression into tokens
        tokens = self.tokenize(expression)
        # Start recursive parsing from token index 0
        self.idx = 0
        return self.helper(tokens, {})

    def tokenize(self, expression: str) -> list:
        # Custom tokenize function that splits expression correctly,
        # accounting for parentheses as separate tokens.
        tokens, i, n = [], 0, len(expression)
        while i < n:
            if expression[i] == ' ':
                i += 1
            elif expression[i] in '()':
                tokens.append(expression[i])
                i += 1
            else:
                # For variables or numbers
                j = i
                while j < n and expression[j] not in " ()":
                    j += 1
                tokens.append(expression[i:j])
                i = j
        return tokens

    def helper(self, tokens: list, env: dict) -> int:
        # If the token is an open parenthesis, process the expression inside.
        if tokens[self.idx] == '(':
            self.idx += 1  # skip '('
            op = tokens[self.idx]  # operator: let, add, or mult
            self.idx += 1  # move past operator
            if op == "let":
                # Create a new environment using the current one as base copy.
                local_env = env.copy()
                # Process variable assignments until we reach the final expression
                while True:
                    # If next token is the closing parenthesis, break.
                    if tokens[self.idx] == ')':
                        # Should not happen here normally.
                        break
                    # Check if we are at the last token for the let expression
                    # by looking ahead: if the token following current is ')', then it is the final expression.
                    # Otherwise, it's a variable.
                    if (self.idx + 1 < len(tokens) and tokens[self.idx+1] != ')' and 
                        tokens[self.idx+1] != '(' and tokens[self.idx+1].lstrip('-').isdigit()) or tokens[self.idx+1] == '(' or tokens[self.idx+1] == "let" or tokens[self.idx+1] == "add" or tokens[self.idx+1] == "mult":
                        # Peek ahead to decide if this is assignment or final expression.
                        # If the next token is not within a pair then treat as variable
                        # We check if there's at least two tokens remaining and the token after is not ')'
                        var = tokens[self.idx]
                        # Look ahead: if the token after variable is ')' then it is not assignment.
                        if tokens[self.idx+1] == ')':
                            # final expression case, so evaluate the variable itself.
                            return self.evaluateVar(tokens[self.idx], local_env)
                        self.idx += 1  # move to expression assigned to var
                        value = self.helper(tokens, local_env)
                        local_env[var] = value
                    else:
                        # Final expression reached
                        result = self.helper(tokens, local_env)
                        self.idx += 1  # skip ')'
                        return result
            elif op == "add":
                # Evaluate left operand
                left = self.helper(tokens, env)
                # Evaluate right operand
                right = self.helper(tokens, env)
                self.idx += 1  # skip ')'
                return left + right
            elif op == "mult":
                # Evaluate left operand
                left = self.helper(tokens, env)
                # Evaluate right operand
                right = self.helper(tokens, env)
                self.idx += 1  # skip ')'
                return left * right
        else:
            # Token can be a number or a variable.
            token = tokens[self.idx]
            self.idx += 1
            # Check if token is a number
            if token.lstrip('-').isdigit():
                return int(token)
            else:
                return env[token]

    def evaluateVar(self, var: str, env: dict) -> int:
        # Helper function to evaluate variable in the given environment.
        return env[var]

# Example usage:
# sol = Solution()
# print(sol.evaluate("(let x 2 (mult x (let x 3 y 4 (add x y))))"))