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.
Some examples:
"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
这道题是之前那道Basic Calculator 基本计算器的拓展，不同之处在于那道题的计算符号只有加和减，而这题加上了乘除，那么就牵扯到了运算优先级的问题，好在这道题去掉了括号，还适当的降低了难度，估计再出一道的话就该加上括号了。不管那么多，这道题先按木有有括号来处理，由于存在运算优先级，我们采取的措施是使用一个栈保存数字，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，那么完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了。代码如下：
class Solution { public: int calculate(string s) { int res = 0, d = 0; char sign = '+'; stack<int> nums; for (int i = 0; i < s.size(); ++i) { if (s[i] >= '0') { d = d * 10 + s[i] - '0'; } if ((s[i] < '0' && s[i] != ' ') || i == s.size() - 1) { if (sign == '+') nums.push(d); if (sign == '-') nums.push(-d); if (sign == '*' || sign == '/') { int tmp = sign == '*' ? nums.top() * d : nums.top() / d; nums.pop(); nums.push(tmp); } sign = s[i]; d = 0; } } while (!nums.empty()) { res += nums.top(); nums.pop(); } return res; } };
本文转自博客园Grandyang的博客，原文链接：基本计算器之二[LeetCode] Basic Calculator II ，如需转载请自行联系原博主。
