227.Basic Calculator II

這題我一開始想要用在學期間所學的, 兩個Stack去完成他, 但除了又臭又長, 非常容易出錯, 直到看討論看到有非常精簡的做法

倘若遇到符號, 就把上一個符號該做的事情處理完,

上一個是+, 沒變動推入這個數

上一個是 -, 把數字變成負數後加入

如果是 *跟除, 那我們就會優先算掉

最後再把stack所有的數字加總即可

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

看到一種不用stack的 , 道理應該是一樣的, 一開始會是+, 後面一次會記錄真正要做的op, 如果也是+, 那我們可以提前先把上一個加總到總和了, 但如果是乘除, 他可能還要面臨接下來的乘除加減, 所以就得留著, 可以run幾個例子會很好懂

class Solution {
  public:
    int calculate(string s) {
        char op = '+';
        int res = 0;
        int cur = 0;
        int num = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = s[i] - '0' + num * 10;
            }
            if (s[i] < '0' && s[i] != ' ' || i == s.size() - 1) {
                switch (op) {
                case '+':
                    cur += num;
                    break;
                case '-':
                    cur -= num;
                    break;
                case '*':
                    cur *= num;
                    break;
                case '/':
                    cur /= num;
                    break;
                }
                if (s[i] == '+' || s[i] == '-' || i == s.size() - 1)          {
                    res += cur;
                    cur = 0;
                }
                op = s[i];
                num = 0;
            }
        }
        return res;
    }
};