题解 | #表达式求值#

解题思路：使用栈

思路：

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

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

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

• 终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。
• 返回值： 将括号内部的计算结果值返回。
• 本级任务： 遍历括号里面的字符，进行计算。

具体做法：

• step 1：使用栈辅助处理优先级，默认符号为加号。
• step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
• step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
• step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
• step 5：最后将栈中剩余的所有元素，进行一次全部相加。

#include <cctype>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    vector<int> function(string s,int index)
    {
        //index为算式的起始下标
        stack<int> stack;
        int num = 0;
        char op = '+';//默认的操作符为'+'
        int i  = 0; 
        int n = s.length();
        for(i = index;i<n;++i)
        {
            //如果是连续的数字则将其转换成对应的数字
            if(isdigit(s[i]))
            {
                num = num * 10 + s[i]-'0';
                if(i != n-1)
                    continue;
            }
            //碰到'('时，把整个括号内的当成一个算式来处理，递归调用function来处理该算式
            if(s[i] == '(')
            {
                //递归处理括号
                vector<int> res = function(s, i+1);
                num = res[0];//获取子算式的结构
                i = res[1];//i更新为')'的位置
                if( i != n-1)
                    continue;
            }
            //查看当前符号，初始默认为+，因为一开始栈为空，只能往里面压入数字
            switch (op) 
            {
                case '+'://加号就压入该数
                    stack.push(num);
                    break;
                case '-'://减号就压入相反数
                    stack.push(-num);
                    break;
                case '*'://乘号就将前一个数弹出然后将相乘的结果压入栈
                    int temp = stack.top();
                    stack.pop();
                    stack.push(num * temp);
                    break;
            }
            num = 0;//操作完一个数以后将其清0
            //出现右括号表示结束递归
            if(s[i] == ')')
                break;
            else //如果不是数字，也不是(),那必定是符号，将符号赋值给op
                op =  s[i];
        }
        int sum = 0;
        //最后将栈中元素都相加就是最终的结果
        while(!stack.empty())
        {
            sum += stack.top();
            stack.pop();
        }
        //返回当前i的位置，在递归函数中是)的位置，但是前面if(s[i] == '(')中在得到当前位置后continue，即将i+1继续下一个字符，所以返回的就是当前位置即可
        return {sum,i};
    }
    int solve(string s) {
        // write code here
        return function(s,0)[0];
    }
};