224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

 1 class Solution {
 2 public:
 3 
 4     int findclose(string s ,int start) {
 5         int level = 0;
 6         for(int i = start;i < s.size(); i++) {
 7             if (s[i]=='(') level++;
 8             if (s[i]==')') {
 9                 level--;
10                 if (level == 0) return i-start;
11             }
12         }
13         return 0;
14     }
15     int help(string s) {
16         int num = 0;
17         int top = 0;
18         char sign = '+';
19         stack<int> stk;
20         for(int i =0;i < s.size();i++) {
21             char ch = s[i];
22             if (isdigit(ch)) {
23                 num  = num*10 + (ch-'0');
24             } 
25             if (ch == '(')  {
26                 int right = findclose(s,i);
27                 num = help(s.substr(i+1,right));
28                 i+=right;
29             }
30             if (!isdigit(ch) || i == s.size()-1) {
31                 if (sign=='+') {
32                     stk.push(num);
33                 } else if (sign == '-') {
34                     stk.push(-num);
35                 } else if (sign == '*') {
36                      top = stk.top();stk.pop();
37                     stk.push(num*top);
38                 } else if (sign == '/') {
39                      top = stk.top();stk.pop();
40                     stk.push(top/num);
41                 }
42                 sign = ch;
43                 num = 0;
44             }
45         }
46         int res = 0;
47         while(!stk.empty()) {
48             res +=stk.top();
49             stk.pop();
50         }
51         return res;
52     }
53     int calculate(string s) {
54         string fs = "" ;
55         for (char ch : s) {
56             if (ch != ' ') {
57                 fs+=ch;
58             }
59         }
60         return help(fs);
61     }
62 };