736. LISP syntax parsing: DFS simulation questions

Title Description

This is a LeetCode Upper 736. Lisp Syntax parsing , The difficulty is difficult .

Tag : 「DFS」、「 simulation 」、「 Hashtable 」

Give you a similar Lisp String expression of statement expression, Calculate the result .

The expression syntax is as follows :

• Expressions can be integers , let expression , add expression , mult expression , Or assigned variable . The result of an expression is always an integer .
• ( Integers can be positive integers 、 Negtive integer 、 )
• let The expression uses   "(let v1 e1 v2 e2 ... vn en expr)" In the form of , among   let Always in string   "let" To express , Next, one or more pairs of alternating variables and expressions will follow , in other words , The first variable   v1 Is assigned as an expression   e1  Value , The second variable   v2  Is assigned as an expression   e2  Value , By analogy ; Final let The value of the expression is   expr Value of expression .
• add The expression is expressed as   "(add e1 e2)" , among   add Always in string   "add" To express , This expression always contains two expressions e1、 e2 , The end result is   e1 The value of the expression and   e2  The value of the expression and .
• mult The expression is expressed as   "(mult e1 e2)" , among   mult Always in string "mult" Express , This expression always contains two expressions e1、e2, The end result is   e1 The value of the expression and   e2  The value of the expression product .
• In this topic , Variable names start with lowercase characters , Follow after One or more lowercase characters or numbers . For convenience , "add" , "let" , "mult" Will be defined as `" keyword " , Will not be used as a variable name .
• Last , Let's talk about the concept of scope . When calculating the expression corresponding to the variable name , In a computational context , First check the innermost scope （ In parentheses ）, Then check the external scopes in order . Every expression in the test case is legal . More details about scope , See example .

Example 1：

Input ：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" Output ：14 explain ： Calculation expression (add x y), Checking variables x When the value of , In the context of variables, the innermost scope checks outward in turn . First find x = 3, So here's x The value is 3 . Example 2：

 Input ：expression = "(let x 3 x 2 x)"

 Output ：2

 explain ：let  The assignment operation in the statement can be processed in sequence .

Example 3：

 Input ：expression = "(let x 1 y 2 x (add x y) (add x y))"

 Output ：5

 explain ：
 first  (add x y)  The result is  3, And assign this value to  x . 
 the second  (add x y)  The result is  3 + 2 = 5 .

Tips ：

• exprssion There are no leading and trailing spaces in
• expressoin Different parts of （ token） Separated by a single space
• The answer is consistent with all intermediate calculations 32-bit Integer range

DFS simulation

I'm not feeling well today , Don't write too detailed , The title is not difficult. , Let's look at it in combination with the code .

Design function int dfs(int l, int r, Map<String, Integer> map) function , For calculation Result , The answer for dfs(0,n-1,map), among Is the length of the string .

Based on the incoming Whether to discuss the expression by case ：

• if , The description is an expression , At that moment, from Start taking back , Until the space is filled （ Suppose the location is idx）, So as to get the operation op（ among op by let、add or mult One of the three ）, here op The corresponding parameter is , That is, you need to skip the position （ That is, skip op Corresponding ) Symbol ）;

  According to op What kind of operation is further processed , Let's design a 「 Pass in the left endpoint and find the right endpoint 」 Function of int getRight(int left, int end), Meaning from left set out , Keep looking right （ No more than end）, Until legal 「 subexpression 」 or 「 Corresponding value 」.

  //  about  getRight  Function function , Let me give you an example    To understand! , In fact, from  left  set out , Find the legal 「 subexpression 」 or 「 value 」 until 
  
  // (let x 2 (mult x (let x 3 y 4 (add x y))))
  //          a                               b
  //  Pass in  a  return  b, representative  [a, b)  Expression for  (mult x (let x 3 y 4 (add x y)))
  
  // (let x 2 (mult x (let x 3 y 4 (add x y))))
  //      ab
  //  Pass in  a  return  b, representative  [a, b)  Expression for  x
  

• otherwise It's not an expression , By judgment Whether it is recorded by hash table to know the result ： If there are records in the hash table , The result is the mapped value in the hash table , Otherwise, the result is the value represented by itself .

We need to pay attention to , according to 「 Scope 」 The definition of , We cannot use global hash tables , When recursing at each level , Pass in clone Coming out map.

Code ：

class Solution {
    char[] cs;
    String s;
    public int evaluate(String _s) {
        s = _s;
        cs = s.toCharArray();
        return dfs(0, cs.length - 1, new HashMap<>());
    }
    int dfs(int l, int r, Map<String, Integer> map) {
        if (cs[l] == '(') {
            int idx = l;
            while (cs[idx] != ' ') idx++;
            String op = s.substring(l + 1, idx);
            r--; //  Judge as  "(let"、"(add"  or  "(mult"  after , Skip the corresponding  ")"
            if (op.equals("let")) {
                for (int i = idx + 1; i <= r; ) {
                    int j = getRight(i, r);
                    String key = s.substring(i, j);
                    if (j >= r) return dfs(i, j - 1, new HashMap<>(map));
                    j++; i = j;
                    j = getRight(i, r);
                    int value = dfs(i, j - 1, new HashMap<>(map));
                    map.put(key, value);
                    i = j + 1;
                }
                return -1; // never
            } else if (op.equals("add")) {
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1, new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return a + b;
            } else {
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1, new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return a * b;
            }
        } else {
            String cur = s.substring(l, r + 1);
            if (map.containsKey(cur)) return map.get(cur);
            return Integer.parseInt(cur);
        }
    }
    int getRight(int left, int end) {
        int right = left, score = 0;
        while (right <= end) {
            if (cs[right] == '(') {
                score++; right++;
            } else if (cs[right] == ')') {
                score--; right++;
            } else if (cs[right] == ' ') {
                if (score == 0) break;
                right++;
            } else {
                right++;
            }
        }
        return right;
    }
}

• Time complexity ： In addition to recursively dividing expressions , There is also a right map Each layer of copy operations , The complexity is
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.736 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases