227. Basic Calculator II.md

227. Basic Calculator II

思路

计算一个简单的算术表达式的值，表达式只包含数字、空格、加减乘除。 此题的难点就在于乘除应该优先计算。

由于乘除优先，所以我们使用一个栈保存计算乘除后的结果，还需要用一个标记记录当前数字前的运算符：

• 若当前数字之前的符号是加，那么把当前数字压入栈中；
• 若当前数字之前的符号是减，那么把当前数字的相反数压入栈中；
• 若当前数字之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中。

这样完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了。

C++

class Solution {
public:
    int calculate(string s) {
        int res = 0, num = 0, n = s.size();
        char op = '+';
        stack<int>stk;
        for(int i = 0; i < n; i++){            
            if(s[i] >= '0' && s[i] <= '9')
                num = 10 * num + (int)(s[i] - '0');

            if(i == n - 1 || s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'){
                if(op == '+') stk.push(num);
                else if(op == '-') stk.push(-1*num);
                else{ // * or /
                    int tmp = stk.top(); stk.pop();
                    if(op == '*') stk.push(tmp * num);
                    else stk.push(tmp / num);
                }
                num = 0;
                op = s[i]; 
            }
        }
        
        while(!stk.empty()){
            res += stk.top();
            stk.pop();
        }
        
        return res;
    }
};