题解 | #表达式求值#

1. 注意各个细节。
   1. 下一个运算符放入之前进行计算。
   2. 左括号进入栈，作为将来运算停止的表示符号。遇到右括号时就会弹出。
   3. 刚开始有可能是负数，那么刚开始push入0.
   4. （-， （+的情况改为(0- (0+
   5. 遇到优先级不够就不要去算，放进去，将来从上往下算就是相当于优先计算。
   6. 最后退出的时候要看看operator栈里面还有没有操作符且不等于“（”
   7. 最后返回栈顶。
   8. 对于数字while循环记得最后i=j，索引复位。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {

        if(!s.size()){
            return 0;
        }

        //删除字符串中所有的空格
        trim(s);
        unordered_map<char,int> priority;
        priority['+'] = 1;
        priority['-'] = 1;
        priority['*'] = 2;
        priority['/'] = 2;

        stack<long> numbers;
        stack<char> operators;

        numbers.push(0);

        for(int i = 0; i< s.length();i++){
            char c = s[i];

            if(c=='('){
                operators.push(c);
            }else if(c==')'){
                while(!operators.empty()){
                    if(operators.top()!='('){
                        compute(numbers,operators);
                    }else{
                        operators.pop();
                        break;
                    }
                }
            }else{
                if(s[i]>='0'&&s[i]<='9'){
                    int num = 0;
                    int j = i;

                    while(j< s.length()&&(s[j]>='0'&&s[j]<='9')){
                        num = num*10 + s[j++]-'0';
                    }
                    i = j-1;//还原当前的索引
                    numbers.push(num);

                }else{//运算符（ + - * / 这一步）
                    if(i>0&&(s[i-1]=='('||s[i-1]=='+'||s[i-1]=='-')){
                        numbers.push(0);
                    }

                    //最开始是没有用算符在栈里面的，只有出现第二个运算符号才进行比较，否则就是把运
                    //运算符放进去，等待接收下一个数字入栈。
                    while(!operators.empty()&&operators.top()!='('){
                        char op = operators.top();
                        //当优先级高的时候，才进行计算。
                        if(priority[op]>=priority[s[i]]){
                            compute(numbers,operators);
                        }else{
                            break;
                        }

                    }
                    operators.push(s[i]);
                }

            }
        }


        while(!operators.empty()&&operators.top()!='(') compute(numbers,operators);

        return numbers.top();

    }


    //删除字符串所有的空格
    void trim(string &s){
        int index = 0;
        if(!s.empty()){
            while((index = s.find(' ',index))!=string::npos){
                s.erase(index,1);
            }
        }
    }


     void compute(stack<long>& number_stack, stack<char>& operator_stack){

         if(number_stack.size()<2 || operator_stack.empty()){
             return;  
         }

         int num2 = number_stack.top();
         number_stack.pop();
         int num1 = number_stack.top();
         number_stack.pop();

         if(operator_stack.top()=='+'){
             number_stack.push(num1+num2);
         }else if(operator_stack.top()=='-'){
             number_stack.push(num1-num2);
         }else if(operator_stack.top()=='*'){
             number_stack.push(num1*num2);
         }else if(operator_stack.top()=='/'){
             number_stack.push(num1/num2);
         }
         operator_stack.pop();
     }

};