Basic Calculator III

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 .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2 " 6-4 / 2 " = 4 "2(5+52)/3+(6/2+8)" = 21 "(2+6 3+5- (314/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.

Solution: Using Stack

We use one stack to store operands, and one to store operators. For each number, we just push it on the stack For operator + and -, we evaluating all previous operators until operators stack is empty or see the bracket. For operator * and /, if the previous operator is +/-, then we just push it to the stack, otherwise we need to evalute the previous operator. For open bracket, we just push it to the stack. For close bracket, we start evaluating all previous ops until we meet the open bracket.

Note: stoi(INT_MAX_Str) will crash, so we need to use long

void helper(stack<char> &operators, stack<long> &operands) {
    char op = operators.top(); operators.pop();
    long rhs = operands.top(); operands.pop();
    long lhs = operands.top(); operands.pop();

    if (op == '+') {
        operands.push( lhs + rhs);
    } else if (op == '-') {
        cout << lhs - rhs << endl;
        operands.push( lhs - rhs);
    } else if (op == '*') {
        operands.push( lhs * rhs);
    } else if (op == '/') {
        operands.push( lhs / rhs);
    }
}

int calculate(string s) {
    stack<char> operators;
    stack<long> operands;
    int i = 0;
    while (i < s.size()) {
        if (isdigit(s[i])) {
            int start = i;
            while (isdigit(s[i])) i++;
            long num = stol(s.substr(start, i-start+1));
            operands.push(num);
            continue;
        } else if (s[i] == '+' || s[i] == '-') {
            while (!operators.empty() && operators.top() != '(' && operators.top() != ')') {
                helper(operators, operands);
            }
            operators.push(s[i]);
        } else if (s[i] == '*' || s[i] == '/') {
            while (!operators.empty() && operators.top() != '(' && operators.top() != ')') {
                if (operators.top() == '+' || operators.top() == '-') break;
                helper(operators, operands);
            }
            operators.push(s[i]);
        } else if (s[i] == '(') {
            operators.push(s[i]);
        } else if (s[i] == ')') {
            while (!operators.empty() && operators.top() != '(' && operators.top() != ')') {
                helper(operators, operands);
            }
            operators.pop();
        }
        i += 1;
    }

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

    cout << operands.top() << endl;
    return (int)operands.top();
}