224. 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-negativeintegers 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

S1: stack O(n)

遇到（时将之前的计算结果和当前符号push进栈

遇到）时计算num栈顶元素，ops栈顶运算符和当前计算结果的运算结果

    int calculate(string s) {
        stack<int> num, ops;
        int curNum = 0, result = 0, sign = 1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == ' ') continue;
            if (s[i] >= '0' && s[i] <= '9') curNum = curNum * 10 + (s[i] - '0');
            else if (s[i] == '(') {
                num.push(result);
                ops.push(sign);
                result = 0;
                sign = 1;
            } else if (s[i] == ')') {
                result += sign * curNum;
                curNum = 0;
                if (!ops.empty()) {
                    result = num.top() + ops.top() * result;
                    num.pop();
                    ops.pop();
                }
            } else {
                result += sign * curNum;
                curNum = 0;
                if (s[i] == '+') sign = 1;
                else sign = -1;
            }
        }
        result += sign * curNum;
        return result;
    }

S2: recursion

碰到括号进入下一层

class Solution {
public:
    int calculate(string s) {
        int i = 0;
        return calcHelper(s, i);
    }

    int calcHelper(string s, int& i) {
        int result = 0, num;
        string numstr = "";
        bool add = true;
        for (; i < s.size(); ++i) {
            if (s[i] == ' ') continue;
            if (s[i] == ')') {
                break;
            } else if (s[i] == '(') {
                numstr = to_string(calcHelper(s, ++i));
            } else if (s[i] >= '0' && s[i] <= '9') {
                numstr += s[i];
            } else {
                num = stoi(numstr);
                result += add? num : -num;
                numstr = "";
                add = s[i] == '+';
            }
        }
        if (numstr.size() != 0) {
            num = stoi(numstr);
            result += add? num : -num;
        }        
        return result;
    }
};