牛客网：表达式求值

计算表达式也是栈/递归的典型应用场景。

首先，如何处理运算符的优先级？乘号显然优先级更高，所以加号和减号运算的结果就直接压栈，直到遇到乘号就取出栈顶然后计算乘的结果再压栈，到最后返回时需要直接求和返回。

其次，我们如何来递归。我们要设置传入参数，这里设置两个参数：字符串和索引。

我们在函数主题中需要完成的任务有

1.如果是数字，需要循环算出数值大小

2.如果是左括号，则递归，这时返回的vector是两个数，一个是这个左括号对应右括号之间的所有项运算的结果，另外一个项是索引位，表示对应的右括号的索引的下一位

3.对运算符进行处理（一开始默认是加号），如果是加减，很明显直接压栈就行，乘则需要和栈顶元素进行运算再压栈

4.如果遇到右括号，则退出当前循环，对栈中元素求和后返回相应vector，否则将运算符更新（记录为当前元素）

代码如下所示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    vector<int> function(string &s, int index){
        stack<int> st;
        char op='+';
        int num=0;
        int i=0;
        for(i=index;i<s.length();++i){
            if(isdigit(s[i])){
                num=num*10+s[i]-'0';
                if(i!=s.length()-1){
                    continue;
                }
            }else if(s[i]=='('){
                vector<int> res=function(s, i+1);
                num=res[0];
                i=res[1];
                if(i!=s.length()-1){
                    continue;
                }
            }
            switch(op){
                case '+':
                    st.push(num);
                    break;
                case '-':
                    st.push(-num);
                    break;
                case '*':
                    int temp=st.top();
                    st.pop();
                    st.push(temp*num);
            }
            num=0;
            if(s[i]==')'){
                break;
            }else{
                op=s[i];
            }
        }
        int sum=0;
        while(!st.empty()){
            sum+=st.top();
            st.pop();
        }
        return vector<int>{sum, i};
    }
    
    int solve(string s) {
        return function(s, 0)[0];
    }
};