題目網址：https://leetcode.cn/problems/evaluate-reverse-polish-notation/

題意：給一 postorder, 返回 inorder 的運算結果。

保證 postorder 運算式皆為有效的, 不會有除數為 0 的情況。

Solution：

想法：利用 Stack, 一旦當前 token 為數字, 則 push 到 stack 中; 否則, 取出 stack 中最上面的兩個 top 元素出來做運算, 並把運算結果 push 到 stack 中。重複以上步驟, 最後 stack 會剩下一個元素, 也就是最終的運算結果

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        for (const auto& token : tokens) {
            if (isdigit(token)) {
                stk.emplace(stoi(token));
            } else {
                // 注意順序
                const int n2 = stk.top();
                stk.pop();

                const int n1 = stk.top();
                stk.pop();

                switch (token[0]) {
                    case '+':
                        stk.emplace(n1 + n2);
                        break;
                    case '-':
                        stk.emplace(n1 - n2);
                        break;
                    case '*':
                        stk.emplace(long(n1) * long(n2));
                        break;
                    case '/':
                        stk.emplace(n1 / n2);
                        break;
                }
            }
        }

        return stk.top();
    }

private:
    stack<int> stk;

    bool isdigit(string& token){
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }
};
  • time：$O(n)$ ➔ for loop, 其中 n 為 token 的個數
  • space：$O(n)$ ➔ stk 中的元素個數不超過 n