题目描述
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-231, 231 - 1] 。
注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval() 。
示例 1：
输入：s = "1+1"
输出：2
示例 2：
输入：s = "6-4/2"
输出：4
示例 3：
输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21
提示：
1 <= s <= 104s 由整数、'+'、'-'、'*'、'/'、'(' 和 ')' 组成s 是一个 有效的 表达式
解法
方法一
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 | class Solution:
def calculate(self, s: str) -> int:
def dfs(q):
num, sign, stk = 0, "+", []
while q:
c = q.popleft()
if c.isdigit():
num = num * 10 + int(c)
if c == "(":
num = dfs(q)
if c in "+-*/)" or not q:
match sign:
case "+":
stk.append(num)
case "-":
stk.append(-num)
case "*":
stk.append(stk.pop() * num)
case "/":
stk.append(int(stk.pop() / num))
num, sign = 0, c
if c == ")":
break
return sum(stk)
return dfs(deque(s))
|
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124 | // 逆波兰表示法求解
class Solution {
public:
// 定义一个操作函数，根据操作符进行数学运算
int operate(int b, char ch, int a) {
// 注意ab顺序
switch (ch) {
case '+':
return a + b; // 加法
case '-':
return a - b; // 减法
case '*':
return a * b; // 乘法
case '/':
return a / b; // 除法
default:
break;
}
return 0; // 默认返回0，处理无效操作符
}
// 计算字符串表达式的值
int calculate(string s) {
int preority[250]; // 操作符优先级数组
preority['+'] = 1;
preority['-'] = 1;
preority['*'] = 2;
preority['/'] = 2;
preority['('] = 0;
preority[')'] = 0;
stack<char> op; // 操作符栈
stack<int> num; // 操作数栈
int stringsize = s.size(); // 字符串长度
int i = 0;
char ch;
// 遍历字符串
for (; i < stringsize; i++) {
ch = s[i];
if (ch == ' ') {
continue; // 跳过空格
}
if (ch >= '0' && ch <= '9') {
int realnum = ch - '0'; // 将字符转换为数字
// 处理多位数字
while (s[i + 1] >= '0' && s[i + 1] <= '9') {
i++;
realnum *= 10;
realnum += s[i] - '0';
}
num.push(realnum); // 将数字压入栈
} else {
// 处理操作符
if (op.empty() || ch == '(' || preority[ch] > preority[op.top()]) {
// 特殊情况，处理首个字符为'-'或'+'的情况
if (num.empty() && (ch == '-' || ch == '+')) {
num.push(0);
}
op.push(ch); // 将操作符压入栈
// 处理括号内的表达式
if (ch == '(') {
int j = i;
while (j + 1 < stringsize) {
// 预处理括号内的首个操作符
if (s[j + 1] == '-' || s[j + 1] == '+') {
num.push(0);
}
if (s[j + 1] != ' ') {
break;
}
j++;
}
}
} else if (ch == ')') {
// 处理右括号
char ch2 = ')';
ch2 = op.top();
op.pop();
while (ch2 != '(') {
int a = num.top();
num.pop();
int b = num.top();
num.pop();
num.push(operate(a, ch2, b)); // 计算并压入结果
ch2 = op.top();
op.pop();
}
} else if (preority[ch] <= preority[op.top()]) {
// 处理优先级小于等于栈顶操作符的情况
char ch2;
ch2 = op.top();
while (!op.empty() && preority[ch] <= preority[op.top()] && ch2 != '(') {
op.pop();
int a = num.top();
num.pop();
int b = num.top();
num.pop();
num.push(operate(a, ch2, b)); // 计算并压入结果
if (!op.empty()) {
ch2 = op.top();
} else {
break;
}
}
op.push(ch); // 将当前操作符压入栈
}
}
}
// 处理剩余在栈中的表达式
while (!op.empty()) {
ch = op.top();
op.pop();
int a = num.top();
num.pop();
int b = num.top();
num.pop();
num.push(operate(a, ch, b)); // 计算并压入结果
}
return num.top(); // 返回最终结果
}
};
|