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 .

Example 1:

Input: "1 + 1" Output: 2 Example 2:

Input: " 2-1 + 2 " Output: 3 Example 3:

Input: "(1+(4+5+2)-3)+(6+8)" Output: 23 Note: You may assume that the given expression is always valid. Do not use the eval built-in library function.

Solution: Using sign

    int calculate(string s) {
        int res = 0, sign = 1, n = s.size();
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0') {
                int num = 0;
                while (i < n && s[i] >= '0') {
                    num = 10 * num + s[i++] - '0';
                }
                res += sign * num;
                --i;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                st.push(res);
                st.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res *= st.top(); st.pop();
                res += st.top(); st.pop();
            }
        }
        return res;
    }

Solution: Using Stack

void helper(stack<int> &operands, stack<char> &operators, unordered_map<char, bool> &basicOps) {
    if (!operators.empty() && basicOps.count(operators.top())) {
        char op = operators.top();
        operators.pop();

        int rhs = operands.top(); operands.pop();
        int lhs = operands.top(); operands.pop();
        int result = 0;

        if (op == '+') {
            result = rhs + lhs;
        } else if (op == '-') {
            result = lhs - rhs;
        }
        operands.push(result);
    }
}

int calculate(string s) {
    if (s.empty()) return 0;

    stack<int> operands;
    stack<char> operators;
    unordered_map<char, bool> basicOps = {{'+', true}, {'-', true}};

    int i=0;
    while (i<s.size()) {
        if (isnumber(s[i])) {
            int start = i;
            while (isnumber(s[i])) i++;
            operands.push(stoi(s.substr(start, i-1)));
            continue;
        } else if (basicOps.count(s[i])) {
            helper(operands, operators, basicOps);
            operators.push(s[i]);
        } else if (s[i] == '(') {
            operators.push(s[i]);
        } else if (s[i] == ')') {
            while (operators.top() != '(') {
                helper(operands, operators, basicOps);
            }
            operators.pop();
        }
    }

    while (!operators.empty()) {
        helper(operands, operators, basicOps);
    }

    return operands.top();
}