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.

Example 1:

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

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

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

Note:

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

• Do not use the eval built-in library function.

op為之前的operator，先處理*和/，然後如果是+和-那把當前數字加上正負號塞入stack，最後把stack裡面的直加總。

int calculate(string s) { // time: O(n); space: O(n)
    if (s.empty()) return 0;
    int n = s.length(), res = 0, num = 0;
    char op = '+';
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
        if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
            if (op == '+') st.push(num);
            else if (op == '-') st.push(-num);
            else if (op == '*' || op == '/') {
                int tmp = (op == '*') ? st.top() * num : st.top() / num;
                st.pop();
                st.push(tmp);
            }
            op = c;
            num = 0;
        }
    }
    while (!st.empty()) {
        res += st.top();
        st.pop();
    }
    return res;
}

+和-之前的數字後面的運算無法影響到他們的值，所以可以不需要stack記錄所有的數字，直接把+和-之前算出來的數字加到global result裡，然後利用curRes取代從stack取top作運算。

int calculate(string s) { // time: O(n); space: O(1)
    if (s.empty()) return 0;
    int res = 0, curRes = 0, num = 0, n = s.length();
    char op = '+';
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
        if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
            switch (op) {
                case '+': curRes += num; break;
                case '-': curRes -= num; break;
                case '*': curRes *= num; break;
                case '/': curRes /= num; break;
            }
            if (c == '+' || c == '-' || i == n - 1) {
                res += curRes;
                curRes = 0;
            }
            op = c;
            num = 0;
        }
    }
    return res;
}