Leetcode227. 基本计算器 II
题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1：
示例 2：
示例 3：
提示：
- 1≤s.length≤3∗105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开s 表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围 [0,231−1] 内
- 题目数据保证答案是一个 32-bit 整数
解题思路
这道题可以运用栈来模拟运算。思路应该说没有什么难度，加减直接压入栈就好，乘除就得先和栈中的顶元素计算，然后压入栈中。最后，将栈中的元素顺序计算就好。关键的难度在于实现，要注意需要将字符串同步转化为整数。
如果用两个栈来实现，可以一个栈存储元素，一个栈来存储运算符。然后按照规则进行模拟。如果用一个栈来模拟，实现上就要麻烦一点。
以字符串"3+2*2"来举例：
首先，将字符串变为"+3+2*2"，在前面加上运算符+。这样，在指针滑动到某个运算符的时候，就可以处理上一个运算符后面，也就是这个运算符前面的元素。但是同时的，当指针滑动到最后的时候，也需要处理最后的一个元素。所以进入这些操作的条件是：
1
| if((!isdigit(s[i]) && s[i] != ' ') || i == s.size() - 1)
|
而对每一个运算符所做的处理为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| switch (op)
{
case '+':
stokens.push(num);
break;
case '-':
stokens.push(-num);
break;
case '*':
pre = stokens.top();
stokens.pop();
stokens.push(pre * num);
break;
case '/':
pre = stokens.top();
stokens.pop();
stokens.push(pre / num);
break;
}
|
也就是加法直接压入元素，减法压入这个 元素的负值，乘除法进行处理后再压入。具体细节见参考代码。
参考代码
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
| int calculate(string s){
if(s.empty()) return 0;
stack<int>stokens;
int num = 0;
char op = '+';
int pre = 0;
for(int i = 0;i < s.size();++i){
if(isdigit(s[i])){
num = num * 10 + (s[i] - '0');
}
if((!isdigit(s[i]) && s[i] != ' ') || i == s.size() - 1){
switch (op)
{
case '+':
stokens.push(num);
break;
case '-':
stokens.push(-num);
break;
case '*':
pre = stokens.top();
stokens.pop();
stokens.push(pre * num);
break;
case '/':
pre = stokens.top();
stokens.pop();
stokens.push(pre / num);
break;
}
op = s[i];
num = 0;
}
}
int ans = 0;
while(!stokens.empty()){
ans += stokens.top();
stokens.pop();
}
return ans;
}
|
复杂度分析
时间复杂度：O(n)，其中 n为字符串 s的长度
空间复杂度：O(n)，其中 n为字符串 s的长度
