227 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.

• You may assume that the given expression is always valid.

Some examples:

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

Solution

class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        vector<int> nums;
        vector<char> signs;
        string tmp = "";
        for ( int i = 0; i < n; i++ ) {
            if ( s[i] == ' ' ) continue;
            if ( s[i] >= '0' and s[i] <= '9' ) { tmp += s[i]; continue;}
            nums.push_back(stoi(tmp));
            signs.push_back(s[i]);
            tmp = "";
        }
        nums.push_back(stoi(tmp));
        n = nums.size() - 1;
        int res = 0, n1 = nums[0];
        for ( int i = 0; i < n; i++ ) {
            if ( signs[i] == '*' ) n1 *= nums[i+1];
            if ( signs[i] == '/' ) n1 /= nums[i+1];
            if ( signs[i] == '+' ) { res += n1; n1 = nums[i+1];}
            if ( signs[i] == '-' ) { res += n1; n1 = -nums[i+1];}
        }
        res += n1;
        return res;
    }
};

Notes

• A valid expression means that the number of "numbers" is larger than the number of "signs" by one. Pre-process the input string to record the numbers and the signs, respectively.
• Note the trick to use a factor to keep track of the + or - sign.

one-pass solution

class Solution {
public:
    int calculate(string s) {
        s = s + '+';
        int n = s.size();
        int res = 0, n1 = 0;
        char sign = '+';
        string tmp = "";
        for ( int i = 0; i < n; i++ ) {
            if ( s[i] == ' ' ) continue;
            if ( s[i] >= '0' and s[i] <= '9' ) { tmp += s[i]; continue;}
            if ( sign == '*' ) n1 *= stoi(tmp);
            if ( sign == '/' ) n1 /= stoi(tmp);
            if ( sign == '+' ) n1 = stoi(tmp);
            if ( sign == '-' ) n1 = -stoi(tmp);
            if ( s[i] == '+' or s[i] == '-' ) res += n1;
            sign = s[i];
            tmp = "";
        }
        return res;
    }
};