表达式求值

思路：

对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。

处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。

处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算：

终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。

返回值： 将括号内部的计算结果值返回。

本级任务： 遍历括号里面的字符，进行计算。

具体做法：

step 1：使用栈辅助处理优先级，默认符号为加号。

step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。

step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。

step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是，则将栈中内容弹出与后一个元素相乘再入栈。*

step 5：最后将栈中剩余的所有元素，进行一次全部相加。

代码：

class Solution {
public:
    //定义一个函数用于求一个表达式的结果
     vector<int> function(string s,int dex){
        //设置一个栈
        stack<int>stack;
        //初始化为+
        char op='+';
        int num=0;
        int i;
        //遍历表达式，只要发现是数字，就将其转化为数字
        //接下来继续看如果还是数字，就说明它和前面的数字是整体
        for(i=dex;i<s.length();i++){
            if(isdigit(s[i])){
                num=num*10+s[i]-'0';
                if(i!=s.length()-1){
                    continue;
                }
            }
            //遍历表达式，如果是左括号，则表示现在求的是就是一个小问题，用递归的方式求
            if(s[i]=='('){
                vector<int>res=function(s,i+1);
                //数组res的第0个数用来存这个表达式的值
                //数组res的第一个数用来存目前求到的表达式的位置
                num=res[0];
                i=res[1];
                //如果解决完这个小问题后，发现还是没有求完表达式，就继续求
                if(i!=s.length()-1){
                    continue;
                }
            }
            //进行分类讨论
            switch(op){
                //如果数字前面是+号，就直接将这个数字压入栈中
            case '+':
                 stack.push(num);
                break;
                //如果是减号，就将其转化为加号进行计算，就是将其相反数压入栈中
            case '-':
                stack.push(-num);
                 break;
                 //如果是乘号，由于其优先级比+和-高，所以将这个数字弹出，将其与这个数进行相乘，再将这个相乘后的结果重新压入栈中
             case '*':
                int temp=stack.top();
                stack.pop();
                stack.push(temp*num);
                break;
            }
            //重新将num初始化为0，用于求后一个数
            num=0;
            //如果遇到右括号，就表示这个小问题已经解决，就递归结束
            if(s[i]==')'){
                break;
            }else{
                //否则就继续运算
                op=s[i];
            }
        }
        //将栈中的所有的元素依次相加，就是表达式的值
        //将表达式的和数组的第0位，将现在求到表达式的位置记录在第一位
            int sum=0;
            while(!stack.empty()){
                sum+=stack.top();
                stack.pop();
            }
            return vector<int>{sum,i};
    
     }
     
    int solve(string s) {
       return function(s,0)[0];
    }
    
};