题解 | 计算器(二)

class Solution {
public:
  //对加法乘除进行优先级的标号
    unordered_map<char, int> order = {
        {'+', 1},
        {'-', 1},
        {'*', 2},
        {'/', 2}
    };

    int calculate(string s) { 
	  //使用两个栈分别存储数字和运算符；
        stack<int> nums;
        stack<char> ops;
        int n = 0;
        bool parsingNumber = false;
		
		//遇到数字进行构造数字，遇到符号进行计算，先计算栈中优先级高或相等的运算符，
		//栈中最多两个运算符,
        for(int i=0; i<s.size(); ++i){
            char c = s[i];

            if(isdigit(c)){
                n = n*10 + (c - '0'); //字符转数字
                parsingNumber = true;
            }

            if(!isdigit(c)  || i==s.size()-1){
                if(parsingNumber){  //数字进栈
                    nums.push(n);
                    n = 0;
                    parsingNumber = false;
                }

                if(i < s.size()-1 || !isdigit(c)){ //计算栈中保留的运算
                    while(!ops.empty() && order[ops.top()] >= order[c]){
                        compute(nums, ops);
                    }
                    ops.push(c);
                }
            }
        }

        while(!ops.empty()){ //可能包含存在
            compute(nums, ops);
        }

        return nums.top();
    }
  
private:
    void compute(stack<int>& nums, stack<char>& ops){
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();

        switch (op) {
            case '+':nums.push(a+b);break;
            case '-':nums.push(a-b);break;
            case '*':nums.push(a*b);break;
            case '/':nums.push(a/b);break;
        }
    }
};