[Leetcode] Basic Calculator, Solution

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

[Thoughts]
一般这种计算器都要依赖于栈来保存上次计算记录，以便来处理括号。在这题里面除了一个栈来保存计算结果，还需要一个栈来保存上一个操作符。


[Code]

1:    int calculate(string s) {  
2:      stack<int> nums, ops;  
3:      int num = 0;  
4:      int total = 0;  
5:      char pre_op = '+';  
6:      for(char c : s) {  
7:        if(isdigit(c)) {  
8:          num = num* 10 + c-'0';  
9:        } else {  
10:          total += (pre_op == '+' ? num:-num);  
11:          num = 0;  
12:          if(c == '(') {  
13:            nums.push(total);  
14:            ops.push(pre_op);  
15:            total = 0;  
16:            pre_op = '+';  
17:          } else if(c == ')') {  
18:            char op = ops.top();  
19:            int temp = nums.top();  
20:            total = (op == '+' ? total:-total) + temp;  
21:            ops.pop();  
22:            nums.pop();  
23:          } else if(c == '+' || c == '-') {  
24:            pre_op = c;  
25:          }     
26:        }  
27:      }  
28:      total += (pre_op == '+' ? num:-num);  
29:      return total;  
30:    }