跳转至

736. Lisp 语法解析

题目描述

给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。

表达式语法如下所示:

  • 表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
  • (整数可以是正整数、负整数、0)
  • let 表达式采用 "(let v1 e1 v2 e2 ... vn en expr)" 的形式，其中 let 总是以字符串 "let"来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量 v1被分配为表达式 e1 的值，第二个变量 v2 被分配为表达式 e2 的值，依次类推；最终 let 表达式的值为 expr表达式的值。
  • add 表达式表示为 "(add e1 e2)" ，其中 add 总是以字符串 "add" 来表示，该表达式总是包含两个表达式 e1、e2 ，最终结果是 e1 表达式的值与 e2 表达式的值之 和 。
  • mult 表达式表示为 "(mult e1 e2)" ，其中 mult 总是以字符串 "mult" 表示，该表达式总是包含两个表达式 e1、e2，最终结果是 e1 表达式的值与 e2 表达式的值之 积 。
  • 在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。为了方便，"add" ，"let" ，"mult" 会被定义为 "关键字" ，不会用作变量名。
  • 最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。

 

示例 1：

输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
输出：14
解释：
计算表达式 (add x y), 在检查变量 x 值时，
在变量的上下文中由最内层作用域依次向外检查。
首先找到 x = 3, 所以此处的 x 值是 3 。

示例 2：

输入：expression = "(let x 3 x 2 x)"
输出：2
解释：let 语句中的赋值运算按顺序处理即可。

示例 3：

输入：expression = "(let x 1 y 2 x (add x y) (add x y))"
输出：5
解释：
第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。 
第二个 (add x y) 计算结果是 3 + 2 = 5 。

 

提示：

  • 1 <= expression.length <= 2000
  • exprssion 中不含前导和尾随空格
  • expressoin 中的不同部分（token）之间用单个空格进行分隔
  • 答案和所有中间计算结果都符合 32-bit 整数范围
  • 测试用例中的表达式均为合法的且最终结果为整数

解法

方法一：递归

时间复杂度 $O(n)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
    def evaluate(self, expression: str) -> int:
        def parseVar():
            nonlocal i
            j = i
            while i < n and expression[i] not in " )":
                i += 1
            return expression[j:i]

        def parseInt():
            nonlocal i
            sign, v = 1, 0
            if expression[i] == "-":
                sign = -1
                i += 1
            while i < n and expression[i].isdigit():
                v = v * 10 + int(expression[i])
                i += 1
            return sign * v

        def eval():
            nonlocal i
            if expression[i] != "(":
                return scope[parseVar()][-1] if expression[i].islower() else parseInt()
            i += 1
            if expression[i] == "l":
                i += 4
                vars = []
                while 1:
                    var = parseVar()
                    if expression[i] == ")":
                        ans = scope[var][-1]
                        break
                    vars.append(var)
                    i += 1
                    scope[var].append(eval())
                    i += 1
                    if not expression[i].islower():
                        ans = eval()
                        break
                for v in vars:
                    scope[v].pop()
            else:
                add = expression[i] == "a"
                i += 4 if add else 5
                a = eval()
                i += 1
                b = eval()
                ans = a + b if add else a * b
            i += 1
            return ans

        i, n = 0, len(expression)
        scope = defaultdict(list)
        return eval()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
    private int i;
    private String expr;
    private Map<String, Deque<Integer>> scope = new HashMap<>();

    public int evaluate(String expression) {
        expr = expression;
        return eval();
    }

    private int eval() {
        char c = expr.charAt(i);
        if (c != '(') {
            return Character.isLowerCase(c) ? scope.get(parseVar()).peekLast() : parseInt();
        }
        ++i;
        c = expr.charAt(i);
        int ans = 0;
        if (c == 'l') {
            i += 4;
            List<String> vars = new ArrayList<>();
            while (true) {
                String var = parseVar();
                if (expr.charAt(i) == ')') {
                    ans = scope.get(var).peekLast();
                    break;
                }
                vars.add(var);
                ++i;
                scope.computeIfAbsent(var, k -> new ArrayDeque<>()).offer(eval());
                ++i;
                if (!Character.isLowerCase(expr.charAt(i))) {
                    ans = eval();
                    break;
                }
            }
            for (String v : vars) {
                scope.get(v).pollLast();
            }
        } else {
            boolean add = c == 'a';
            i += add ? 4 : 5;
            int a = eval();
            ++i;
            int b = eval();
            ans = add ? a + b : a * b;
        }
        ++i;
        return ans;
    }

    private String parseVar() {
        int j = i;
        while (i < expr.length() && expr.charAt(i) != ' ' && expr.charAt(i) != ')') {
            ++i;
        }
        return expr.substring(j, i);
    }

    private int parseInt() {
        int sign = 1;
        if (expr.charAt(i) == '-') {
            sign = -1;
            ++i;
        }
        int v = 0;
        while (i < expr.length() && Character.isDigit(expr.charAt(i))) {
            v = v * 10 + (expr.charAt(i) - '0');
            ++i;
        }
        return sign * v;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    int i = 0;
    string expr;
    unordered_map<string, vector<int>> scope;

    int evaluate(string expression) {
        expr = expression;
        return eval();
    }

    int eval() {
        if (expr[i] != '(') return islower(expr[i]) ? scope[parseVar()].back() : parseInt();
        int ans = 0;
        ++i;
        if (expr[i] == 'l') {
            i += 4;
            vector<string> vars;
            while (1) {
                string var = parseVar();
                if (expr[i] == ')') {
                    ans = scope[var].back();
                    break;
                }
                ++i;
                vars.push_back(var);
                scope[var].push_back(eval());
                ++i;
                if (!islower(expr[i])) {
                    ans = eval();
                    break;
                }
            }
            for (string v : vars) scope[v].pop_back();
        } else {
            bool add = expr[i] == 'a';
            i += add ? 4 : 5;
            int a = eval();
            ++i;
            int b = eval();
            ans = add ? a + b : a * b;
        }
        ++i;
        return ans;
    }

    string parseVar() {
        int j = i;
        while (i < expr.size() && expr[i] != ' ' && expr[i] != ')') ++i;
        return expr.substr(j, i - j);
    }

    int parseInt() {
        int sign = 1, v = 0;
        if (expr[i] == '-') {
            sign = -1;
            ++i;
        }
        while (i < expr.size() && expr[i] >= '0' && expr[i] <= '9') {
            v = v * 10 + (expr[i] - '0');
            ++i;
        }
        return sign * v;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
func evaluate(expression string) int {
    i, n := 0, len(expression)
    scope := map[string][]int{}

    parseVar := func() string {
        j := i
        for ; i < n && expression[i] != ' ' && expression[i] != ')'; i++ {
        }
        return expression[j:i]
    }

    parseInt := func() int {
        sign, v := 1, 0
        if expression[i] == '-' {
            sign = -1
            i++
        }
        for ; i < n && expression[i] >= '0' && expression[i] <= '9'; i++ {
            v = (v * 10) + int(expression[i]-'0')
        }
        return sign * v
    }

    var eval func() int
    eval = func() int {
        if expression[i] != '(' {
            if unicode.IsLower(rune(expression[i])) {
                t := scope[parseVar()]
                return t[len(t)-1]
            }
            return parseInt()
        }
        i++
        ans := 0
        if expression[i] == 'l' {
            i += 4
            vars := []string{}
            for {
                v := parseVar()
                if expression[i] == ')' {
                    t := scope[v]
                    ans = t[len(t)-1]
                    break
                }
                i++
                vars = append(vars, v)
                scope[v] = append(scope[v], eval())
                i++
                if !unicode.IsLower(rune(expression[i])) {
                    ans = eval()
                    break
                }
            }
            for _, v := range vars {
                scope[v] = scope[v][:len(scope[v])-1]
            }
        } else {
            add := expression[i] == 'a'
            if add {
                i += 4
            } else {
                i += 5
            }
            a := eval()
            i++
            b := eval()
            if add {
                ans = a + b
            } else {
                ans = a * b
            }
        }
        i++
        return ans
    }
    return eval()
}

评论