Leetcode刷题笔记题解（C++）：224. 基本计算器

思路：

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

#include <stack>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int calculate(string s) {
        // write code here
        return function(s, 0)[0];
    }

    vector<int> function(string s,int index){
        stack<int>sk;
        long long num = 0;
        char op = '+';
        int i;
        for(i = index;i<s.size();i++){
            if(s[i]==' ') continue;
            //如果当前为数字
            else if(s[i]>='0'&&s[i]<='9'){
                num = num*10+s[i]-'0';//防止连续的数字
                if(i!=s.length()-1&&s[i+1]!=' ') continue;//如果为数字不执行下面的语句继续遍历,并且下一个字符不为空格
            }
            else if(s[i]=='('){//遇到左括号，从左括号开始第一个进行递归,并且下一个字符不为空格
                vector<int> res = function(s, i+1);
                num = res[0];//计算出括号中的计算值
                i = res[1];//得出遍历的下标位置
                if(i!=s.length()-1&&s[i+1]!=' ') continue;//如果还没结束字符串则继续遍历
            }
            switch (op) {
                case '+':
                    sk.push(num);
                    break;
                case '-':
                    sk.push(0-num);
                    break;
                case '*':
                    int temp = sk.top();
                    sk.pop();
                    sk.push(temp*num);
                    break;
            
            }
            num = 0;
            if(s[i] == ')') break;//遇到右括号则递归结束
            else op = s[i];
        }
        int sum = 0;
        //计算栈中的所有值的和
        while (!sk.empty()) {
            sum += sk.top();
            sk.pop();
        }
        return vector<int> {sum,i};
    }
};