一、题目
1 <= s.length <= 3 ∗ 1 0 5 3 * 10^53∗10
5
s 由整数和算符 (’+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数
二、思路
（1）首先考虑最简单的情况，只有加减法，如3-4+5，首先给第一个数字加上默认初始化的符号+，即+3-4+5，拆分为+3，-4，+5，依次放入栈中求和即得结果。
（2）接着考虑乘除法情况，比如3-4*9+5则需要先求出乘法后再继续像（1）一样进栈相加运算。即直接在switch中加上乘除法的case。
（3）最后一种情况是有括号时，因为括号有递归性质，如3-(1-4*9)+5需要先处理括号内容，其中也有乘法和减法。
c a l c u l a t e （ 3 − ( 1 − 4 ∗ 9 ) + 5 ） calculate（3-(1-4*9)+5）calculate（3−(1−4∗9)+5）
= 3 − c a l c u l a t e ( 1 − 4 ∗ 9 ) + 5 = 3- calculate(1-4*9)+5=3−calculate(1−4∗9)+5
= 3 − ( − 35 ) − 6 = 3 - (-35)-6=3−(−35)−6
即无论有多少层括号的嵌套，都可以通过caculate函数递归调用自己，将括号内容计算成一个数字。
还有一种方法是常规的双栈操作。
三、C++代码
class Solution { public: int calculate(string s) { int begin = 0; return calHelper(s, begin); } //i用于记录计算开始的索引 int calHelper(string s, int& i){ stack<int> stk; char sign = '+'; int num = 0; for(int i = 0; i < s.size(); i++){ //把str类型转为数字 char c = s[i]; if(isdigit(c)){ num = 10 * num + (c - '0'); } if(c == '('){ //从i的下一个开始计算，进入递归 num = calHelper(s, ++i); //计算完之后的i指向)所以再++ i++; } //如果不是数字，或者不是空格 if((!isdigit(c) && c != ' ') || i >= s.size() - 1){ switch(sign){ int pre; //拿出前一个数字做对应运算 case '+': stk.push(num); break; case '-': stk.push(-num); break; case '*': //top返回栈顶元素 pre = stk.top(); stk.pop(); stk.push(pre * num); break; case '/': pre = stk.top(); stk.pop(); stk.push(pre / num); break; //更新符号为当前符号，数字清零 } sign = c; num = 0; } //遇到)则回到上一级递归 if(s[i] == ')'){ break; } } //将栈中所有结果求和即答案 int res = 0; while(!stk.empty()){ res += stk.top(); stk.pop(); } return res; } };
