一、题目

• 1 <= s.length <= $3\ast 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需要先处理括号内容，其中也有乘法和减法。
$calculate（3-(1-4\ast 9)+5）$
$=3-calculate(1-4\ast 9)+5$
$=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;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/122452974