Title LeetCode 736 hard

Give you a string expression similar to Lisp statement and find its calculation result.

The expression syntax is as follows:

Expressions can be integers, let expressions, add expressions, mult expressions, or assigned variables. The result of an expression is always an integer.
(integer can be positive integer, negative integer, 0)
Let expression is in the form of "(let v1 e1 v2 e2... VN en expr)", where "let" is always represented by the string "let", followed by one or more pairs of alternating variables and 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 expression is the value of the expr expression.
The add expression is expressed as "(add e1 e2)", where "add" is always represented by the string "add". The expression always contains two expressions e1 and e2. The final result is the sum of the value of the expression e1 and the value of the expression e2.
The mult expression is expressed as "(mult e1 e2)", where "mult" is always represented by the string "mult". The expression always contains two expressions e1 and e2. The final result is the product of the value of the expression "e1" and the value of the expression "e2".
In this topic, variable names start 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 be used as variable name.
Finally, 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. Every expression in the test case is legal. For more details on scopes, see examples.

 
Example 1:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y)))"
Output: 14
Explanation:
Calculate the expression (add x y). When checking the value of variable x,
In the context of variables, the innermost scope checks outward in turn.
First find x = 3, so the x value here is 3.
Example 2:

Input: expression = "(let x 3 x 2 x)"
Output: 2
Explanation: the assignment operation in the let statement can be processed in order.
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 to 3 and assigns this value to X.
The second (add x y) calculation is 3 + 2 = 5.

Source: LeetCode
Link: https://leetcode-cn.com/problems/parse-lisp-expression

 

Thinking process:

For students who don't know lisp and the compilation principle of parser, it doesn't affect them. We just need to look at the topic definition. Now that we have defined part of the syntax of this language, all you have to do is use the language you're good at to analyze its three expressions, add, mult and let, step by step

First of all, let's design an addition calculator. What would you do, for example, 1 + 1 =?

You must think how simple it is. Just extract the three characters' 1 '+' 1 'and add up the numbers. Yes, that's it

For the addition of multiple numbers, such as 1 + 1 + 1, your idea should remain unchanged, but in the process of parsing, you will find that a '+' is actually redundant. You only need + 1. This is actually a prefix expression, which is more important to facilitate calculation

Then look at the expressions in the title (add E1, E2). Isn't that (+ 1, 1)? Well, let's continue, improve the difficulty and replace it with add+

(add (add 1 1) 2) is to calculate the previous + 1 1 first, and then add the result to the following 2. Smart you may think of using stack or recursion. According to the law of recursion, you will find that (+ 1 1) is essentially a number and an addition formula,

The stack implementation is even simpler. Enter the stack from left to right, record "(add" and perform a calculation when the corresponding ")" is encountered

Let's first write a converter to save the elements according to the style we want. If we don't need this step, we can directly take the elements into and out of the stack. However, although this will increase an traversal, it will be easier to reuse and clearer later:

Define keywords first, including those that will be used later:

    static final String ADD = "(add";
    static final String MULT = "(mult";
    static final String LET = "let";
    static final String END = ")";
    static final String SPACE = " ";

/**
     * For example, extract (add 1 (add 1 1)) and others (add, 1, (add, 1,1,),), for clarity, some APIs have high complexity and lexer processing
     */
    static List<String> convert(String exp) {
        List<String> list = new ArrayList<>();
        while (!exp.isEmpty()) {
            String e = null;
            if (exp.startsWith(ADD)) {
                e = ADD;
            } else if (exp.startsWith(END)) {
                e = END;
            } else {
                // As number
                // Non final parameter,Then it's the end of the space
                int endSpace = exp.indexOf(SPACE);
                // There is no space behind it, which means it's coming to an end
                if (endSpace < 1) {
                    endSpace = Integer.MAX_VALUE;
                }
                // The last argument is parentheses")"ending
                int endBrackets = exp.indexOf(END);
                e = exp.substring(0, Math.min(endSpace, endBrackets));
            }
            list.add(e);
            exp = exp.substring(e.length()).trim();
        }
        return list;
    }

Test this method. We can make a complex "(add (add (add 1 1) (add (add 1 1) 1)) (add 2 1))", and the output is no problem as follows. Pay attention to the processing of spaces, which are all in accordance with the correct display requirements of the title

 

Then start our core parse process, adopt the iteration (stack) mentioned above, and implement it separately from recursion. Here, we put parsing and first calculation together. Note:

    static int parseAndEvaluate(String exp){
        Deque<String> stack = new ArrayDeque<>();
        // take exp Organize the elements
        List<String> tokenList = convert(exp);
        for(String e : tokenList) {
            if (e.equals(END)) {
                // Take out the elements for calculation,Get"(add"until
                int a = 0;
                String b = stack.pop();
                while (!b.equals(ADD)) {
                    int c = Integer.parseInt(b);
                    // calculation
                    a+=c;
                    // Continue fetching data elements
                    b = stack.pop();
                }
                stack.push(String.valueOf(a));
            } else {
                // Add element
                stack.push(e);
            }
        }
        // exp If the data is correct,Only one element in the stack is the final result
        return Integer.parseInt(stack.pop());
    }

 

 

Test "(add (add (add 1 1) (add (add 1 1) 1)) (add 2 1))", the title only stipulates that add has two parameters, which directly supports more parameters

 

As for the implementation of recursion, it is also possible to directly process tokenList, but we want to change the way. We try to build a data structure, Enode, how to build it. We observe (add 1 1 1), the whole can be regarded as an Enode, which mainly includes three parts. add 1 1,add as the operator, and this "1" may also be (add 1 1 1), that is, an Enode, Then we can start to define this specific data structure:

class Enode {
    // type by add perhaps mult Design according to the topic eNodes Length 2,However, we directly handle it to support multiple parameters
    // type by let When, eNodes,The length of the design is variable according to the topic
    // type When it is a variable or value, eNodes Empty, content Variable name or value
    String type;
    List<Enode> eNodes;
    // Content, such as a b c, 1 2 3
    String content;

    // local variable,add,mult Time value,adopt let Operation to store
    Map<String, Integer> envMap;
}

Smart, you will think that this is not the data structure of n-ary tree. envMap we will ignore first

After the node data structure of the tree is designed, we can start to build the tree. We can call the tokenList obtained by convert to help us build the tree, or directly build it during convert:

    Enode getType(String e) {
        Enode node = new Enode();
        // Non value type
        if (e.startsWith("(add") || e.startsWith("(mult") || e.startsWith("(let")) {
            if (e.startsWith("(add")) {
                node.type = "(add";
            } else if (e.startsWith("(mult")) {
                node.type = "(mult";
            } else if (e.startsWith("(let")) {
                node.type = "(let";
            }
            List<Enode> list = new ArrayList<>();
            node.eNodes = list;
            e = e.substring(node.type.length(), e.length() - 1).trim();
            for (int i = 0; i < e.length(); i++) {
                if (e.charAt(i) == ' ') continue;
                String ex = "" + e.charAt(i);
                int c = i;
                if (ex.charAt(0) == '(') {
                    int left = 1;
                    for (int j = c + 1; j < e.length(); j++) {
                        i++;
                        ex += e.charAt(j);
                        if (e.charAt(j) == '(') {
                            left++;
                        } else if (e.charAt(j) == ')') {
                            left--;
                            if (left == 0) {
                                break;
                            }
                        }
                    }
                } else {
                    for (int j = c + 1; j < e.length(); j++) {
                        i++;
                        if (e.charAt(j) == ' ') {
                            break;
                        } else {
                            ex += e.charAt(j);
                        }
                    }
                }
                list.add(getType(ex));
            }
            return node;
        }
        try {
            // Value type
            Integer.parseInt(e);
            node.type = "val";
        } catch (Exception ex) {
            // variable,Exception handling is used here,Not recommended,Regular can be used for type determination,for convenience
            node.type = "par";
        }
        node.content = e;
        return node;
    }

As for let,let, when we perform the assignment operation, we use an envMap to maintain the variable kv. When entering the next environment, we will copy the envMap. If the child environment is re assigned, it will not affect the envMap of the parent environment. The following is the calculation process, which is to traverse the multi fork tree,

Here is the recursive processing:

    int evaluateNode(Enode node) {
        switch (node.type) {
            case "val":
                return Integer.parseInt(node.content);
            case "par":
                return node.envMap.get(node.content);
            case "(add":
                int sum = 0;
                for (int i = 0; i < node.eNodes.size(); i++) {
                    Enode node2 = node.eNodes.get(i);
                    node2.envMap = node.envMap;
                    sum += evaluateNode(node2);
                }
                return sum;
            case "(mult":
                int mult = 1;
                for (int i = 0; i < node.eNodes.size(); i++) {
                    Enode node2 = node.eNodes.get(i);
                    node2.envMap = node.envMap;
                    mult *= evaluateNode(node2);
                }
                return mult;
            case "(let":
                Map<String, Integer> envMap = new HashMap<>();
                if (node.envMap != null) {
                    envMap.putAll(node.envMap);
                }
                for (int i = 0; i < node.eNodes.size() - 1; i += 2) {
                    Enode node2 = node.eNodes.get(i + 1);
                    node2.envMap = envMap;
                    envMap.put(node.eNodes.get(i).content, evaluateNode(node2));
                }
                Enode result = node.eNodes.get(node.eNodes.size() - 1);
                result.envMap = envMap;
                // System.out.println(envMap);
                return evaluateNode(result);
        }
        return 0;
    }

Finally, write the calling function to test:

    public int evaluate(String e) {
        Enode root = getType(e);
        return evaluateNode(root);
    }

, compared with the original topic, we add add and mult multi parameter support

Thank you. It's not very detailed. I'll write some related later to supplement. We can learn from each other and have a happy New Year!