LeetCode 736. LISP syntax parsing

736. Lisp Syntax parsing

 

【DFS】 String parsing + recursive

First extract the operator , Later, it will be split according to the concept of sub expression , Put it in a list in .

If the operator is let, So two by two traversal , The first string is used as key, The second string is an expression , Continue recursive parsing , Take the return value as value Deposit together map in . Then return the parsed value of the last string .

If the operator is add, Then you only need to add the parsing results of the two expressions to return .

The operator is mult Empathy .

class Solution {

    // dfs 9:32 11:00
    int ans = 0;

    int dfs(Map<String, Integer> map, String ex) {
        if ((ex.charAt(0) >= '0' && ex.charAt(0) <= '9') || ex.charAt(0) == '-') {
            return Integer.parseInt(ex);
        }
        if (ex.charAt(0) == '(') {
            ex = ex.substring(1, ex.length() - 1);
        }
        // System.out.println(ex);
        // for (var k: map.keySet()) {
        //     System.out.print(k + "," + map.get(k) + ";");
        // }
        // System.out.println();
        int n = ex.length(), i = 0, j = 0;
        while (j < n && ex.charAt(j) != ' ') {
            j++;
        } 
        List<String> list = new ArrayList();
        String op = ex.substring(i, j);
        i = ++j;
        int t = 0;
        char c;
        if (op.equals("let")) {
            while (i < n) {
                while (j < n) {
                    c = ex.charAt(j);
                    if (t != 0) {
                        if (c == ')') {
                            t--;
                        } else if (c == '(') {
                            t++;
                        }
                    } else {
                        if (c == '(') {
                            t++;
                        } else if (c == ' ') {
                            break;
                        }
                    }
                    j++;
                }
                list.add(ex.substring(i, j));
                i = ++j;
            }
            int m = list.size() - 1;
            Map<String, Integer> next = new HashMap(map);
            for (i = 0; i < m; i += 2) {
                char ch = list.get(i + 1).charAt(0);
                if ((ch >= '0' && ch <= '9') || ch == '-') {
                    next.put(list.get(i), Integer.parseInt(list.get(i + 1)));
                } else {
                    next.put(list.get(i), dfs(next, list.get(i + 1)));
                }
            }
            ans = dfs(next, list.get(m));
            return ans;
        } else if (op.equals("add") || op.equals("mult")) {
            while (i < n) {
                while (j < n) {
                    c = ex.charAt(j);
                    if (t != 0) {
                        if (c == ')') {
                            t--;
                        } else if(c == '(') {
                            t++;
                        }
                    } else {
                        if (c == '(') {
                            t++;
                        } else if (c == ' ') {
                            break;
                        }
                    }
                    j++;
                }
                list.add(ex.substring(i, j));
                i = ++j;
            }
            int ret = 0;
            if (op.equals("add")) {
                for (var e: list) {
                    if (map.containsKey(e)) {
                        ret += map.get(e);
                    } else {
                        ret += dfs(map, e);
                    }
                }
            } else {
                ret = 1;
                for (var e: list) {
                    if (map.containsKey(e)) {
                        ret *= map.get(e);
                    } else {
                        ret *= dfs(map, e);
                    }
                }
            }
            return ret;
        } else {
            // System.out.println(op);
            return map.get(op);
        }
    }

    public int evaluate(String expression) {
        Map<String, Integer> map = new HashMap();
        return dfs(map, expression);
        // return ans;
    }
}