1. Problem Description:

Given an expression similar to Lisp statement, calculate its calculation result. The expression syntax is as follows:
Expressions can be integers, let syntax, add syntax, mult syntax, or assigned variables. The result of an expression is always an integer. (integers can be positive integers, negative integers, 0)
Let syntax is expressed as (let v1 e1 v2 e2... VN en expr), where let syntax is always represented by the string "let", followed by one or more alternating variables or expressions, that is, the first variable v1 is assigned as the value of expression e1 ， the second variable v2 is assigned as the value of expression e2 ， and so on; The value of the final let syntax is the value of the expr expression.
The add syntax is expressed as (add e1 e2). The add syntax is always represented by the string "add". The syntax always has two expressions e1 and e2. The final result of the syntax is the sum of the value of the expression e1 and the value of the expression e2.
The mult syntax is expressed as (mult e1 e2), where the "mult" syntax is always represented by the string "mult". The syntax always has two expressions e1 and e2. The final result of the syntax is the product of the value of the "e1" expression and the value of the "e2" expression.
In this topic, the naming of variables starts with lowercase characters, followed by 0 or more lowercase characters or numbers. For convenience, "add", "let", "mult" will be defined as "keyword" and will not appear in the variable name of the expression.
Finally, let's talk about the concept of scope. When calculating the expression corresponding to the variable name, in the calculation context, first check the innermost scope (in parentheses), and then check the external scope in order. We will ensure that the expression of each test is legal. For more detailed information about the scope, see the example.

Example:

Input: (add 1 2)
Output: 3

Input: (mult 3 (add 2 3))
Output: 15

Input: (let x 2 (mult x 5))
Output: 10

Input: (let x 2 (mult x (let x 3 y 4 (add x y)))
Output: 14
Explanation:
Expression (add x y). When obtaining the x value, we should calculate outward from the innermost layer in turn. First, we encounter x=3, so the x value here is 3

Input: (let x 3 x 2 x)
Output: 2
Explanation: the assignment operation in the let statement can be processed in order

Input: (let x 1 y 2 x (add x y) (add x y))
Output: 5
Explanation:
The first (add x y) evaluates to 3 and assigns this value to X.
The second (add x y) calculation result is 3 + 2 = 5.

Input: (let x 2 (add (let x 3 (let x 4 x)) x))
Output: 6
Explanation:
The scope of X in (let x 4 x) is only within (). So in the final addition operation, the value of X is 2.

Input: (let a1 3 b2 (add a1 1) b2)
Output: 4
Explanation:
Variable names can be followed by numbers after the first lowercase letter

be careful:

The expression expressions given by us are formatted: there is no extra space before and after the expression, only one space is used between different parts of the expression (keywords, variables, expressions), and there is no space between adjacent parentheses. The expressions we give are legal and the final result is an integer. The maximum length of the expression we give is 2000 (the expression will not be empty because it is not a legal expression). The final result and the intermediate calculation result will be a 32-bit integer.
Source: LeetCode
Link: https://leetcode-cn.com/problems/parse-lisp-expression

2. Train of thought analysis:

Analysis of the topic shows that this topic is similar to Li Kou's 726 Questions belong to the problem of bracket nesting. For this kind of bracket nesting problem, we can generally use recursion to solve it, because bracket nesting itself is a recursive process. When we recursively solve the expression result, we first solve the value of the innermost bracket expression, and then return to the previous layer to continue solving until we reach the outermost bracket. Lisp expression is actually a recursive process, so it can be solved by recursion. Firstly, the expression is a sequence of parentheses, so we need to skip the left parenthesis at the beginning, and then intercept the first three characters to judge which operation is it: let/add/mult. For let operation, there are multiple groups of variables and expression values, and the value of the last expression is the result of let sentence, so we solve the values corresponding to these variables and store them in a hash table, For the add operation, we need to solve the value of two addends. The addition of the two addends is the result of add. For the mult operation, we need to solve two multipliers. The multiplication of the two multipliers is the result of mult. We need to declare a global variable k to record the recursive position. In this way, when we return to the previous layer, the current recursive position is the latest, When solving, you need to skip the characters such as spaces or brackets. In addition, this topic also involves a scope problem. It can be found that the scope of the variable in the bracket is within the whole bracket. When the bracket is out, the current variable has no function, so the scope of the variable in the bracket is within the whole bracket; After solving the value corresponding to the variable, we store it in the hash table (the python language is used here, so the dictionary is used to store the value of the key value pair). Moreover, a bracket belongs to a scope. Therefore, before using the get method to solve the bracket expression, we use the copy method in Python to copy the dictionary. In this way, when we call down recursively, the value of the key value pair in the previous bracket will not be affected. The copy method belongs to deep copy Bei, it will only be copied to the parent directory, and this topic happens to be a key corresponding to a value, so the modification of the dictionary in parentheses will not affect the value of the key value pair outside parentheses. In fact, it copies a copy of the dictionary after solving the parenthesis expression.

3. The code is as follows:

class Solution:
    k = 0

    def get(self, s: str, dic: dict):
        val = 0
        if s[self.k] == "-" or "0" <= s[self.k] <= "9":
            # Solve the corresponding number
            u = self.k + 1
            while "0" <= s[u] <= "9": u += 1
            val = int(s[self.k: u])
            self.k = u
        # The current expression is a variable. We can get the name of the variable and then take it out of the hash table
        elif s[self.k] != "(":
            name = ""
            u = self.k
            while s[u] != ")" and s[u] != " ": u += 1
            name = s[self.k: u]
            self.k = u
            val = dic[name]
        # If the current expression is a bracket expression, you need to call the dfs method to find the corresponding value
        else:
            # You need to copy a copy of the dictionary before recursive calls, so that the modification of key value pairs during recursive calls will not affect the values of key value pairs outside the current brackets
            dic2 = dic.copy()
            t = self.dfs(s, dic2)
            return t
        return val

    def dfs(self, s: str, dic: dict):
        val = 0
        # Skip current left parenthesis
        self.k += 1
        # Intercept the first three characters to determine which operation it belongs to
        t = s[self.k: self.k + 3]
        if t == "let":
            # Skip let s and spaces
            self.k += 4
            # The key value pairs are stored in the dictionary (hash table)
            while self.k < len(s):
                name = ""
                # The name corresponding to the v at the end of the space is not found when there is a closing parenthesis
                while s[self.k] != " " and s[self.k] != ")":
                    name += s[self.k]
                    self.k += 1
                # The current is the closing parenthesis, indicating that it is over
                if s[self.k] == ")":
                    val = dic[name]
                    break
                # Skip spaces
                self.k += 1
                # Solve the value of v, v can be a number or an expression, so you can use a method to solve the corresponding value of e
                val = self.get(s, dic)
                # Skip spaces
                self.k += 1
                # Store key value pairs in a hash table
                dic[name] = val
                # Judge whether it is the last expression of let statement. The last expression can be - / number or left parenthesis
                if s[self.k] == "(" or s[self.k] == "-" or "0" <= s[self.k] <= "9":
                    val = self.get(s, dic)
                    break
        # The current operation is add
        elif t == "add":
            # Skip add and spaces
            self.k += 4
            # Solve the value of the first addend
            a = self.get(s, dic)
            # Skip spaces
            self.k += 1
            # Solve the value of the second addend
            b = self.get(s, dic)
            val = a + b
        else:
            # Skip mult and spaces
            self.k += 5
            a = self.get(s, dic)
            self.k += 1
            b = self.get(s, dic)
            val = a * b
        # Skip the currently matching closing bracket
        self.k += 1
        return val

    def evaluate(self, s: str) -> int:
        dic = dict()
        return self.dfs(s, dic)