leetcode 224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包括左括号（，右括号），加号 +，减号 -，非负整数和空格。

解：用一个栈stack<char> op存储表达式中的运算符，一个栈stack<int> num存储表达式中的数字

 1 class Solution {
 2 public:
 3     int calculate(string s) {
 4         stack<char> op;
 5         stack<int> num;
 6         for(int i = 0; i < s.size(); ++ i)
 7         {
 8             char c = s[i];
 9             if(c == ' ') continue;
10             if(c == '+' or c == '-' or c == '(') op.push(c);
11             else if(c == ')')
12             {
13                 op.pop();
14                 if(op.size() and op.top() != '(') calc(op, num);
15             }
16             else
17             {
18                 int cur = 0;
19                 while(i < s.size() and isdigit(s[i])) 
20                 {
21                     cur = cur * 10 + (s[i] - '0');
22                     ++ i;
23                 }
24                 i = i - 1;
25                 num.push(cur);
26                 if(op.size() and op.top() != '(') calc(op, num);
27             }
28         }
29         return num.top();
30     }
31 
32     void calc(stack<char> &op, stack<int> &num)
33     {
34         int y = num.top();
35         num.pop();
36         int x = num.top();
37         num.pop();
38         if(op.top() == '+') num.push(x + y);
39         else num.push(x - y);
40         op.pop();
41     }
42 };