Basic Calculator

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

此题的关键是维护一个正负号表
我们以一个例子来看待这个问题
3-(2+(9-4))

我们可以将这个式子拆分成两部分即3 和 -(2+(9-4))，我们定义全局的正负属性为正,现在只需要分别计算出这两部分的值就好
对于3我们可以看成是+3,也就是说我们以正负号来划分基本的计算单元(例如+3)，这样我们只需要知道这个计算单元的正负属性就好了，例如对于-(2+(9-4))，我们可以知道括号内所有的小的计算单元的全局属性就是负号。
我们看一下这个式子展开的过程,一个计算单元计算完毕（数字完毕或者遇到右括号）后，记得弹出该计算单元对应的符号


 remaining   sign stack      total
3-(2+(9-4))   [1, 1]            0
 -(2+(9-4))   [1]               3
  (2+(9-4))   [1, -1]           3
   2+(9-4))   [1, -1, -1]       3
    +(9-4))   [1, -1]           1
     (9-4))   [1, -1, -1]       1
      9-4))   [1, -1, -1, -1]   1
       -4))   [1, -1, -1]      -8
        4))   [1, -1, -1, 1]   -8
         ))   [1, -1, -1]      -4
          )   [1, -1]          -4
              [1]              -4

class Solution {
public:
    int calculate(string s) {
        stack<int> sign;

        sign.push(1);
        sign.push(1);

        int ret = 0;
        for(size_t i = 0; i < s.size(); ++i){
            int num = 0;
            if(isdigit(s[i])){
                num =  s[i] -'0';

                while(i+1 < s.size() && isdigit(s[i+1])){
                    num = num * 10 + s[i+1] - '0';
                    ++i;
                }

                ret += sign.top()*num;
                sign.pop();

            }else if(s[i] == '+' || s[i] == '('){
                sign.push(1 * sign.top());
            }else if(s[i] == '-'){
                sign.push(-1 * sign.top());
            }else if(s[i] == ' ' || s[i] == '\t'){
                continue;
            }else{
                sign.pop();
            }
        }

        return ret;
    }
};