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 herereturn 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};}
};