Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

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

Example 1:

Input: "3+2*2" Output: 7 Example 2:

Input: " 3/2 " Output: 1 Example 3:

Input: " 3+5 / 2 " Output: 5

Solution: Using Stack

void helper(stack<char> &ops, stack<int> &operands) {    
    if (ops.empty()) return;

    int rhs = operands.top(); operands.pop();
    int lhs = operands.top(); operands.pop();
    char op = ops.top(); ops.pop();

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

int calculate(string s) {
    stack <char> ops;
    stack <int> operands;

    int i=0;
    while (i < s.size()) {
        if (isdigit(s[i])) {
            int start = i;
            while (isdigit(s[i])) i++;
            int num = stoi(s.substr(start, i-start+1));
            operands.push(num);
            continue;
        } else if (s[i] == '+' || s[i] == '-') {
            while (!ops.empty()) {
                helper(ops, operands);
            }
            ops.push(s[i]);
        } else if (s[i] == '*' || s[i] == '/') {
            if (!ops.empty() && ops.top() != '+' && ops.top() != '-') {
                helper(ops, operands);
            }
            ops.push(s[i]);
        }
        i += 1;
    }

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

    return operands.top();
}