LeetCode 736. Lisp 语法解析

736. Lisp 语法解析

 

【DFS】字符串解析+递归

首先提取出操作符后，后面按照子表达式的概念进行拆分，拆分后放在一个list中。

如果操作符为let，那么两两遍历，第一个字符串作为key，第二个字符串是一个表达式，继续递归解析，将返回值作为value一起存入map中。然后返回最后一个字符串的解析值。

如果操作符为add，那么只需要将两个表达式的解析结果相加返回。

操作符为mult同理。

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;
    }
}