224. Basic Calculator (Hard)

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.

Solution 1: Stack 15ms

int calculate(string s) {
    stack<int> signs, nums;
    int ans = 0, sign = 1, result = 0;
    for (int i = 0; i < s.size(); ++i) {
        switch (s[i]) {
            case ' ': break; //skip space
            case '+': sign = 1; break;
            case '-': sign = -1; break;
            case '(': 
                //push current calculated result and latest sign on the stack
                nums.push(result); signs.push(sign);
                result = 0; sign = 1;
                break;
            case ')': 
                //pop off from the stack and combine with the result in braces
                result = nums.top()+signs.top()*result;
                nums.pop(); signs.pop();
                break;
            default:
                int num = 0;
                while (i < s.size()  &&  s[i] >= '0')
                    num = 10*num+s[i++]-'0';
                result += sign*num;
                --i;
                break;

        }
    }

    return result;
}

Solution 2:

Keep a global running total and a stack of signs (+1 or -1), one for each open scope. The "global" outermost sign is +1.

• Each number consumes a sign.
• Each + and - causes a new sign.
• Each ( duplicates the current sign so it can be used for the first term inside the new scope. That's also why I start with [1, 1] - the global sign 1 and a duplicate to be used for the first term, since expressions start like 3... or (..., not like +3... or +(....
• Each ) closes the current scope and thus drops the current sign.

Example trace:

Here's an example trace for input 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

这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个一维的符号数组来记录加减号，然后我们开始遍历字符串表达式，如果遇到的是数字，则从符号数组中取出最后一个符合和数字运算后更新结果，如果遇到右括号，则移除一个符号，如果遇到的不是空格，即有可能是加减号或是左括号，则符号数组中加1或-1，做个判断，如果是负号，加个-1，其他情况加1。代码如下：

int calculate(string s) {
    vector<int> signs(2,1);
    int res = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] >= '0') {
            int num = 0;
            while (i < s.size() && s[i] >= '0') {
                num = 10*num+s[i++]-'0';
            }
            res += signs.back()*num; 
            signs.pop_back();
            --i;
        } else if (s[i] == ')') {
            signs.pop_back();
        } else if (s[i] != ' ') {
            signs.push_back(signs.back()*(s[i] == '-' ? -1:1));
        }
    }

    return res;
}