leetcode 227. Basic Calculator II [Medium]

題目敘述

輸入算式的字串，返回解答。運算子只有 +, -, *, /，這題還沒有出現包含括號的情況。

解題紀錄

這次直覺用 stack 解出來，但仔細想想其實不一定需要 stack，應該也可以用幾個變數代替。之後有空再補上。

class Solution {
public:
    int calculate(string s) {
        long long int tmp;
        long long int num = 0;
        int len = s.size();
        
        stack<long long int> result;
        char op_code = '+';
        
        for (int i = 0; i < len; ++i) {
            if (isnumber(s[i])) {
                num = num * 10 + s[i] - '0';
            } 
            
            if (!isnumber(s[i]) && s[i] != ' ' || i == len-1) {
                switch (op_code) {
                    case '+':
                        result.push(num);
                        break;
                    case '-':
                        result.push(-num);
                        break;
                    case '*':
                        tmp = result.top() * num;
                        result.pop();
                        result.push(tmp);
                        break;
                    case '/':
                        tmp = result.top() / num; 
                        result.pop();
                        result.push(tmp);
                        break;
                }
                num = 0;
                op_code = s[i];
            }
        }
        
        while (!result.empty()) {
            num += result.top();
            result.pop();
        }
        return num;
    }
    
    bool isnumber(const char c) {
        return c >= '0' && c <= '9';
    }
};

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

執行時間:

過幾天會補上不用 stack 的解法，目前還沒想到比較乾淨的寫法。