150. Evaluate Reverse Polish Notation

150. Evaluate Reverse Polish Notation

這個題目是屬於如何使用 Stack 來紀錄處理四則運算的方法。Wiki：逆波蘭表示法，在逆波蘭記法中，所有運算子置於運算元的後面，因此也被稱為字尾表示法、後序表示法。逆波蘭記法不需要括號來標識運算子的優先級。

逆波蘭表達式的直譯器一般是基於堆疊的。解釋過程一般是：運算元入棧；遇到運算子時，運算元出棧，求值，將結果入棧；當一遍後，棧頂就是表達式的值。因此逆波蘭表達式的求值使用堆疊結構很容易實現，並且能很快求值。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            if token in "+-*/":
                a = stack.pop()
                b = stack.pop()
                if token == '+':
                    stack.append(a + b)
                elif token == '*':
                    stack.append(a * b)
                elif token == "-":
                    stack.append(b - a)
                elif token == '/':
                    stack.append(int(b/a))
            else:
                stack.append(int(token))
        return stack.pop()

時間複雜度為 O(n)

空間複雜度為 O(n)