问题
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.
You may assume that the given expression is always valid.
例子
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
分析
1 使用istringstream，将字符串变成字符流，自动分割字符串并直接转换成数字或字符
2 使用栈，保存表达式中的数字或者两个数字*/的结果
3 遍历栈，将栈元素依次相加即可得到表达式的计算结果
举个例子，对于表达式3-5/2，首先初始化运算符为+号，即表达式变成+3-5/2；将+3压入栈，-5压入栈，发现下一个运算符是/，将-5出栈，将-5/2=-2入栈。
要点
- istringstream可以处理任意多空格分割的字符串
- 用栈来保存上一步的数字
- 用vector模拟栈
时间复杂度
O(n)
空间复杂度
O(n)
代码
class Solution {
public:
int calculate(string s) {
vector<int> stk;
istringstream iss(s);
char op = '+';
int res = 0, term;
while (iss >> term) {
if (op == '+' || op == '-') {
stk.push_back(op == '+' ? term : -term);
}
else {
int last = stk.back();
stk.pop_back();
stk.push_back(op == '*' ? last * term : last / term);
}
iss >> op;
}
for (int num : stk)
res += num;
return res;
}
};
