友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
224. 基本计算器
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval()。
示例 1：
输入：s = "1 + 1" 输出：2
示例 2：
输入：s = " 2-1 + 2 " 输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23
提示：
-
1 <= s.length <= 3 * 105 -
s由数字、+、-、(、)、和 ` ` 组成 -
s表示一个有效的表达式 -
+不能用作一元运算(例如，+1和+(2 + 3)无效) -
-可以用作一元运算(即-1和-(2 + 3)是有效的) -
输入中不存在两个连续的操作符
-
每个数字和运行的计算将适合于一个有符号的 32位 整数
思路分析
使用双栈来分别存数字和操作符。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-30 07:42:31
*/
public int calculate(String s) {
// 存放所有的数字
Deque<Integer> nums = new ArrayDeque<>(s.length());
// 存放所有的操作，包括 +/-
Deque<Character> ops = new ArrayDeque<>(s.length());
// 为了防止第一个数为负数，先往 nums 加个 0
nums.offerLast(0);
// 将所有的空格去掉
s = s.replaceAll(" ", "");
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '(') {
ops.offerLast(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
if (ops.peekLast() != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (Character.isDigit(c)) {
int num = c - '0';
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (i + 1 < chars.length && Character.isDigit(chars[i + 1])) {
num = num * 10 + chars[i + 1] - '0';
i++;
}
nums.offerLast(num);
} else {
if (i > 0 && (chars[i - 1] == '-' || chars[i - 1] == '+' || chars[i - 1] == '(')) {
nums.offerLast(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
while (!ops.isEmpty() && ops.peekLast() != '(') {
calc(nums, ops);
}
ops.offerLast(c);
}
}
}
while (!ops.isEmpty()) {
calc(nums, ops);
}
return nums.peekLast();
}
private void calc(Deque<Integer> nums, Deque<Character> ops) {
if (nums.isEmpty() || nums.size() < 2) {
return;
}
if (ops.isEmpty()) {
return;
}
Integer a = nums.pollLast();
Integer b = nums.pollLast();
Character op = ops.pollLast();
nums.offerLast(op == '+' ? a + b : b - a);
}