227. Basic Calculator II (Medium)

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.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

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

Solution 1: Stack 13ms

class Solution {
public:
    int calculate(string s) {
        int num = 0;
        char sign = '+';
        stack<int> nums;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = s[i++]-'0';
                while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
                    num = 10*num+s[i++]-'0';
                }
            } 
            if (s[i] != ' ' || i == s.size()-1) {
                if (sign == '+') nums.push(num);
                else if (sign == '-') nums.push(-num);
                else if (sign == '*' || sign == '/') {
                    int tmp = sign == '*' ? nums.top()*num:nums.top()/num;
                    nums.pop();
                    nums.push(tmp);
                }
                sign = s[i];
                num = 0;
            }
        }
        int res = 0;
        while (!nums.empty()) {
            res += nums.top();
            nums.pop();
        }
        return res;
    }
};

Expension: Solution 2: