基本计算器
1.题目内容
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
示例 2：
示例 3：
1
2
| 输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
|
提示：
1 <= s.length <= 3 * 105s 由数字、'+'、'-'、'('、')'、和 ' ' 组成s 表示一个有效的表达式- ‘+’ 不能用作一元运算(例如， “+1” 和
"+(2 + 3)" 无效)
- ‘-‘ 可以用作一元运算(即 “-1” 和
"-(2 + 3)" 是有效的)
- 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
2.解法
双栈
思路及算法
我们可以使用两个栈 nums 和 ops 。
nums ： 存放所有的数字ops ：存放所有的数字以外的操作，+/- 也看做是一种操作
然后从前往后做，对遍历到的字符做分情况讨论：
- 空格 : 跳过
( : 直接加入 ops 中，等待与之匹配的 )) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums- 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入
nums
+/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums
一些细节：
- 由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往
nums 添加一个 0
- 为防止
()内出现的首个字符为运算符，将所有的空格去掉，并将(-替换为 (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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| //C++
class Solution {
public:
void replace(string& s){
int pos = s.find(" ");
while (pos != -1) {
s.replace(pos, 1, "");
pos = s.find(" ");
}
}
int calculate(string s) {
// 存放所有的数字
stack<int> nums;
// 为了防止第一个数为负数，先往 nums 加个 0
nums.push(0);
// 将所有的空格去掉
replace(s);
// 存放所有的操作，包括 +/-
stack<char> ops;
int n = s.size();
for(int i = 0; i < n; i++) {
char c = s[i];
if(c == '(')
ops.push(c);
else if(c == ')') {
// 计算到最近一个左括号为止
while(!ops.empty()) {
char op = ops.top();
if(op != '(')
calc(nums, ops);
else {
ops.pop();
break;
}
}
}
else {
if(isdigit(c)) {
int cur_num = 0;
int j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while(j <n && isdigit(s[j]))
cur_num = cur_num*10 + (s[j++] - '0');
// 注意上面的计算一定要有括号，否则有可能会溢出
nums.push(cur_num);
i = j-1;
}
else {
if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
nums.push(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
while(!ops.empty() && ops.top() != '(')
calc(nums, ops);
ops.push(c);
}
}
}
while(!ops.empty())
calc(nums, ops);
return nums.top();
}
void calc(stack<int> &nums, stack<char> &ops) {
if(nums.size() < 2 || ops.empty())
return;
int b = nums.top(); nums.pop();
int a = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
nums.push(op == '+' ? a+b : a-b);
}
};
|
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
| //Java
class Solution {
public int calculate(String s) {
// 存放所有的数字
Deque<Integer> nums = new ArrayDeque<>();
// 为了防止第一个数为负数，先往 nums 加个 0
nums.addLast(0);
// 将所有的空格去掉
s = s.replaceAll(" ", "");
// 存放所有的操作，包括 +/-
Deque<Character> ops = new ArrayDeque<>();
int n = s.length();
char[] cs = s.toCharArray();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.addLast(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
char op = ops.peekLast();
if (op != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (isNum(c)) {
int u = 0;
int j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (j < n && isNum(cs[j])) u = u * 10 + (int)(cs[j++] - '0');
nums.addLast(u);
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.addLast(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
ops.addLast(c);
}
}
}
while (!ops.isEmpty()) calc(nums, ops);
return nums.peekLast();
}
void calc(Deque<Integer> nums, Deque<Character> ops) {
if (nums.isEmpty() || nums.size() < 2) return;
if (ops.isEmpty()) return;
int b = nums.pollLast(), a = nums.pollLast();
char op = ops.pollLast();
nums.addLast(op == '+' ? a + b : a - b);
}
boolean isNum(char c) {
return Character.isDigit(c);
}
}
|
复杂度分析