题目描述
给定一个字符串 expression 表示以简化形式嵌套的数学表达式。
一个 合法 表达式要么是一个整数 字面量，要么符合 op(a,b) 格式，其中：
op 是 "add"，"sub"，"mul"，"div" 中的一个。a 和 b 都是合法表达式。
运算符 定义如下：
add(a,b) = a + bsub(a,b) = a - bmul(a,b) = a * bdiv(a,b) = a / b
返回一个整数，表示在完全计算表达式后的结果。
示例 1：
输入：expression = "add(2,3)"
输出：5
解释：
运算 add(2,3) 表示 2 + 3 = 5。
示例 2：
输入：expression = "-42"
输出：-42
解释：
这个表达式是单个整数字面量，所以结果是 -42。
示例 3：
输入：expression = "div(mul(4,sub(9,5)),add(1,1))"
输出：8
解释：
- 首先，计算内部表达式：
sub(9,5) = 9 - 5 = 4 - 接下来，将结果相乘：
mul(4,4) = 4 * 4 = 16 - 然后，计算右边的加法：
add(1,1) = 1 + 1 = 2 - 最后，将两个主要结果相除：
div(16,2) = 16 / 2 = 8
因此，整个表达式的结果是 8。
提示：
1 <= expression.length <= 105expression 是有效的，由数字、逗号、括号、减号 '-' 和小写字符串 "add"，"sub"，"mul"，"div" 组成。- 所有中间结果都位于长整型的范围内。
- 所有除法运算结果都是整数值。
解法
方法一：递归
我们定义一个递归函数 \(\text{parse}(i)\)，用于解析从索引 \(i\) 开始的子表达式并返回计算结果以及下一个未处理的索引位置。那么答案为 \(\text{parse}(0)[0]\)。
函数 \(\text{parse}(i)\) 的实现如下：
- 如果当前位置 \(i\) 处是一个数字或负号
-，则继续向后扫描直到遇到非数字字符，解析出一个整数并返回该整数以及下一个未处理的索引位置。 - 否则，当前位置 \(i\) 处是一个操作符
op 的起始位置，我们继续向后扫描直到遇到左括号 (，解析出操作符字符串 op。然后跳过左括号，递归调用 \(\text{parse}\) 解析第一个参数 \(a\)，再跳过逗号，递归调用 \(\text{parse}\) 解析第二个参数 \(b\)，最后跳过右括号 )。 - 根据操作符
op，计算 \(a\) 和 \(b\) 的结果，并返回该结果以及下一个未处理的索引位置。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(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 | class Solution:
def evaluateExpression(self, expression: str) -> int:
def parse(i: int) -> (int, int):
if expression[i].isdigit() or expression[i] == "-":
j = i
if expression[j] == "-":
j += 1
while j < len(expression) and expression[j].isdigit():
j += 1
return int(expression[i:j]), j
j = i
while expression[j] != "(":
j += 1
op = expression[i:j]
j += 1
val1, j = parse(j)
j += 1
val2, j = parse(j)
j += 1
res = 0
match op:
case "add":
res = val1 + val2
case "sub":
res = val1 - val2
case "mul":
res = val1 * val2
case "div":
res = val1 // val2
return res, j
return parse(0)[0]
|
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 | class Solution {
private String expression;
public long evaluateExpression(String expression) {
this.expression = expression;
return parse(0)[0];
}
private long[] parse(int i) {
if (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '-') {
int j = i;
if (expression.charAt(j) == '-') {
j++;
}
while (j < expression.length() && Character.isDigit(expression.charAt(j))) {
j++;
}
long num = Long.parseLong(expression.substring(i, j));
return new long[] {num, j};
}
int j = i;
while (expression.charAt(j) != '(') {
j++;
}
String op = expression.substring(i, j);
j++;
long[] result1 = parse(j);
long val1 = result1[0];
j = (int) result1[1];
j++;
long[] result2 = parse(j);
long val2 = result2[0];
j = (int) result2[1];
j++;
long res = 0;
switch (op) {
case "add":
res = val1 + val2;
break;
case "sub":
res = val1 - val2;
break;
case "mul":
res = val1 * val2;
break;
case "div":
res = val1 / val2;
break;
}
return new long[] {res, j};
}
}
|
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 | class Solution {
public:
long long evaluateExpression(string expression) {
auto parse = [&](this auto&& parse, int i) -> pair<long long, int> {
if (isdigit(expression[i]) || expression[i] == '-') {
int j = i;
if (expression[j] == '-') {
j++;
}
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
long long num = stoll(expression.substr(i, j - i));
return {num, j};
}
int j = i;
while (expression[j] != '(') {
j++;
}
string op = expression.substr(i, j - i);
j++;
auto [val1, next_j1] = parse(j);
j = next_j1 + 1;
auto [val2, next_j2] = parse(j);
j = next_j2 + 1;
long long res = 0;
if (op == "add") {
res = val1 + val2;
} else if (op == "sub") {
res = val1 - val2;
} else if (op == "mul") {
res = val1 * val2;
} else if (op == "div") {
res = val1 / val2;
}
return {res, j};
};
return parse(0).first;
}
};
|
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 | func evaluateExpression(expression string) int64 {
var parse func(int) (int64, int)
parse = func(i int) (int64, int) {
if expression[i] >= '0' && expression[i] <= '9' || expression[i] == '-' {
j := i
if expression[j] == '-' {
j++
}
for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
j++
}
num, _ := strconv.ParseInt(expression[i:j], 10, 64)
return num, j
}
j := i
for expression[j] != '(' {
j++
}
op := expression[i:j]
j++
val1, nextJ1 := parse(j)
j = nextJ1 + 1
val2, nextJ2 := parse(j)
j = nextJ2 + 1
var res int64
switch op {
case "add":
res = val1 + val2
case "sub":
res = val1 - val2
case "mul":
res = val1 * val2
case "div":
res = val1 / val2
}
return res, j
}
result, _ := parse(0)
return result
}
|
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 | function evaluateExpression(expression: string): number {
function parse(i: number): [number, number] {
if (/\d/.test(expression[i]) || expression[i] === '-') {
let j = i;
if (expression[j] === '-') {
j++;
}
while (j < expression.length && /\d/.test(expression[j])) {
j++;
}
const num = +expression.slice(i, j);
return [num, j];
}
let j = i;
while (expression[j] !== '(') {
j++;
}
const op = expression.slice(i, j);
j++;
const [val1, nextJ1] = parse(j);
j = nextJ1 + 1;
const [val2, nextJ2] = parse(j);
j = nextJ2 + 1;
let res: number;
switch (op) {
case 'add':
res = val1 + val2;
break;
case 'sub':
res = val1 - val2;
break;
case 'mul':
res = val1 * val2;
break;
case 'div':
res = Math.floor(val1 / val2);
break;
default:
res = 0;
}
return [res, j];
}
return parse(0)[0];
}
|