{x}
blog image

Parse Lisp Expression

You are given a string expression representing a Lisp-like expression to return the integer value of.

The syntax for these expressions is given as follows.

  • An expression is either an integer, let expression, add expression, mult expression, or an assigned variable. Expressions always evaluate to a single integer.
  • (An integer could be positive or negative.)
  • A let expression takes the form "(let v1 e1 v2 e2 ... vn en expr)", where let is always the string "let", then there are one or more pairs of alternating variables and expressions, meaning that the first variable v1 is assigned the value of the expression e1, the second variable v2 is assigned the value of the expression e2, and so on sequentially; and then the value of this let expression is the value of the expression expr.
  • An add expression takes the form "(add e1 e2)" where add is always the string "add", there are always two expressions e1, e2 and the result is the addition of the evaluation of e1 and the evaluation of e2.
  • A mult expression takes the form "(mult e1 e2)" where mult is always the string "mult", there are always two expressions e1, e2 and the result is the multiplication of the evaluation of e1 and the evaluation of e2.
  • For this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally, for your convenience, the names "add", "let", and "mult" are protected and will never be used as variable names.
  • Finally, there is the concept of scope. When an expression of a variable name is evaluated, within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on the scope.

 

Example 1:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14
Explanation: In the expression (add x y), when checking for the value of the variable x,
we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate.
Since x = 3 is found first, the value of x is 3.

Example 2:

Input: expression = "(let x 3 x 2 x)"
Output: 2
Explanation: Assignment in let statements is processed sequentially.

Example 3:

Input: expression = "(let x 1 y 2 x (add x y) (add x y))"
Output: 5
Explanation: The first (add x y) evaluates as 3, and is assigned to x.
The second (add x y) evaluates as 3+2 = 5.

 

Constraints:

  • 1 <= expression.length <= 2000
  • There are no leading or trailing spaces in expression.
  • All tokens are separated by a single space in expression.
  • The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer.
  • The expression is guaranteed to be legal and evaluate to an integer.

Solution Explanation

This problem involves parsing Lisp-like expressions, which requires handling nested expressions, variable assignments (with scoping), and arithmetic operations. The solution uses a recursive approach with a helper function eval to traverse and evaluate the expression.

Approach

  1. Recursive eval Function: The core of the solution is the recursive eval function. It handles different expression types:

    • Variable: If the current character is a lowercase letter, it parses the variable name, retrieves its value from the scope (a dictionary/hash map storing variable values), and returns the value.
    • Integer: If the current character is a digit or a minus sign, it parses the integer and returns it.
    • let Expression: If it encounters a let expression, it processes variable assignments sequentially. For each variable, it evaluates its expression, stores the result in the scope, and adds it to the stack. After all assignments, it evaluates the final expression and returns the result. Importantly, it cleans up the scope after evaluating the let expression by removing the temporarily added variables. This manages the scope correctly.
    • add/mult Expressions: For add and mult expressions, it recursively evaluates the two subexpressions and performs the corresponding arithmetic operation.

  2. Helper Functions: Helper functions like parseVar and parseInt assist in parsing variable names and integers from the input string, respectively.

  3. Scope Management: The scope dictionary/hash map is crucial for managing variable scopes. It's a stack-like data structure. When a let expression is encountered, the variables are added to the scope with their evaluated values. After the let expression is processed, these variables are removed from the scope to ensure correct scoping. The last added value for a variable will be retrieved if the variable is encountered in a nested expression.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the input expression. The recursive eval function visits each character in the expression at most once.
  • Space Complexity: O(N) in the worst case. The space complexity is mainly determined by the recursive call stack and the scope dictionary/hash map. In the worst case, a deeply nested expression could lead to a stack of size O(N) and potentially O(N) variables stored in scope.

Code Explanation (Python)

The Python code effectively implements this approach. Let's break down key parts:

def evaluate(self, expression: str) -> int:
    # ... (helper functions parseVar, parseInt) ...
 
    def eval():
        nonlocal i  # Access and modify the outer 'i'
        # ... (Variable and Integer handling) ...
 
        if expression[i] == 'l': #let expression
            # ... (process let expression, manage scope using scope[var].append/pop) ...
 
        else:  # add or mult expression
            # ... (process add/mult, recursively call eval) ...
 
        return ans
    # ... (initialization, call eval, return result) ...

The nonlocal i statement is essential. It allows the inner function eval to modify the i variable of the outer evaluate function, enabling the traversal of the input string. The scope dictionary keeps track of variable values within their scopes. The code meticulously handles scope using append and pop operations on the lists in scope to simulate stack-like behavior for each variable.

The other language implementations (Java, C++, Go) follow a similar structure and logic, adapting the syntax and data structures to their respective languages. The core concept of recursive evaluation and scope management remains consistent across all implementations.