[LeetCode]227. Basic Calculator II

Problem

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Example 1:

Input: "3+2*2"
Output: 7
Example 2:

Input: " 3/2 "
Output: 1
Example 3:

Input: " 3+5 / 2 "
Output: 5
Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution

Analysis

数值计算.题目说明,字符串中包括0-9数字,+,-,*,/,以及空格’ ‘, 不包含字母以及括号. 一种方法,可以将字符串转换成逆波兰表达式,然后再计算. 另一种方法是使用栈,直接计算.但是这里还设计到运算符优先级的问题.

这里使用一个栈结构,存入数字,同时,把”+”和”-“纳入数字中,”-“,相当于加上”-num”; 同时注意,数字并不一定是0-9范围内,可能是2位数或更高; 另外, 需要确定什么时候对数字进行计算. 设计到优先级的问题. 比较上一个运算符和当前运算符之间的优先级,如果上一个运算符是”+”或者”-“, 将这个数字(两个运算符之间的数字,也就是上一个运算符针对的这个数字), 然后更新运算符; 如果上一个运算符是”*”或者”/“, 需要从数字栈中弹出一个数字,和当前数字,根据上一个运算进行运算,然后把运算结果压入数据栈, 更新运算符.

最后数据栈中,对应的运算都是+加法运算,依次弹出,直到数据栈为空,返回计算结果.

Code

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
class Solution {
public:
int calculate(string s) {
long result = 0, num = 0, n = s.size();
stack<int> data;
char op = '+';

for (int i=0; i< n; i++){
if (s[i] >= '0')//计算当前运算针对的数字
num = num * 10 + s[i] - '0';
if ((s[i] < '0' && s[i] != ' ') || i == n-1){
if (op == '+') data.push(num);
else if (op == '-') data.push(-num);
else if (op == '*' || op == '/'){
int temp = (op == '*' ? data.top()*num : data.top()/num);
data.pop();
data.push(temp);
}
op = s[i];
num = 0;
}
}

while (!data.empty()){
result += data.top();
data.pop();
}
return result;
}
};

References

https://www.cnblogs.com/grandyang/p/4601208.html

您的支持就是我更新的最大动力!谢谢!