题目描述
给定一个包含正整数、加(+)、减(-)、乘()、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例：
输入: "3+2*2"
输出: 7
输入: " 3/2 "
输出: 1
输入: " 3+5 / 2 "
输出: 5
说明：
- 你可以假设所给定的表达式都是有效的。
- 请不要使用内置的库函数 eval。
思路
因为表达式不包含负数并且给定的表达式是有效的，所以第一个数字为正数。定义栈 valStack 用来存储中间结果，记录两个变量：num 表示当前的数字，op 表示运算符。nums 初始化为 0，op 初始化为 +。算法如下：
-
遍历字符串：
- 如果当前字符是数字，则将数字加入到 num 中，注意，参与运算的数字可能不止一位；
- 如果当前字符不是数字并且不是空格：
- 如果 op=='+'，则将 num 压入 valStack 中，将 num 重置为 0；
- 如果 op=='-'，则将 -num 压入 valStack，将 num 重置为 0；
- 如果 op=='*'||op=='/'，则将 valStack 的栈顶元素出栈，记为 preNum，记为前一个数字。如果是乘，就将 preNum*num 入栈；如果是除，就将 preNum/num 入栈。入栈后将 num 重置为 0。
- 更新 op 为当前字符。
-
栈 valStack 中的元素相加就是结果。
需要注意的是，op 是当前数字前的操作符，例如，123+456-789，当得到当前数字 456 之后，当前的字符为 -，此时 op 为 456 前的字符 +，所以将 456 入栈（而不是 -456）,然后将 op 更新为 -，代表下一个数字的符号。代码如下：
class Solution {
public:
int calculate(string s) {
if(s.empty()) return 0;
char op = '+';
long num = 0;
stack<long> valStack;
for(int i=0; i<=s.length(); i++){ // 是 <=，不是 <，因为使用 <，最后一个数字不会被算到结果当中，所以使用 <=
if(i<s.length() && isdigit(s[i])) num = num * 10 + s[i] - '0'; // 数字可能不止一位
else if(s[i]!=' '){
if(op=='+'){
valStack.push(num);
num = 0;
}else if(op=='-'){
valStack.push(-num);
num = 0;
}else{
int preNum = valStack.top(); valStack.pop();
if(op=='*'){
valStack.push(preNum * num);
num = 0;
}else if(op=='/'){
valStack.push(preNum / num);
num = 0;
}
}
op = s[i];
}
}
long ans = 0;
while(!valStack.empty()){
ans += valStack.top();
valStack.pop();
}
return ans;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)