224. Basic Calculator

The basic idea behind is consider subtraction as an alternative of addition. Subtraction becomes addition of product of sign and number.  So the operation becomes generic, i.e. num*sign. As a result, we need to stacks to keep sum so far and the sign for next number/sum ("next" here means the number in process or the sum in parentheses). I've tried to make it clear in the code.

When I revisited this problem I missed line 30.

1:  class Solution {  
2:  public:  
3:    int calculate(string s) {  
4:      stack<int> nums, ops;  
5:      int res = 0, num = 0, sign = 1;  
6:      for (char c : s) {  
7:        if (c >= '0' && c <= '9') num = num * 10 + c - '0';  
8:        else {  
9:          res += num*sign;  
10:          num = 0;  
11:          if (c == '+') sign = 1;  
12:          else if (c == '-') sign = -1;  
13:          else if (c == '(') {  
14:            // at this point, the expression become "res '+/-' ("  
15:            // and we want to compute the value in parenthese.  
16:            // We can consider a brand new express in parenthese.  
17:            ops.push(sign);  
18:            nums.push(res);  
19:            res = 0;  
20:            sign = 1;  
21:          } else if (c == ')') {  
22:            // at this point, we've got (res), we need to remove the parenthese  
23:            // and compute (last res) '+/-' (res)  
24:            res = ops.top()*res + nums.top();  
25:            nums.pop();  
26:            ops.pop();  
27:          }  
28:        }  
29:      }  
30:      res += sign * num;  
31:      return res;  
32:    }  
33:  };