LeetCode: 150-Evaluate Reverse Polish Notation 解題紀錄

Last Updated on 2022-12-17 by Clay

題目

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

題目輸入是一串字串陣列，陣列是全用字串表示的『數值』（可能包含負數）和『運算子』（加減乘除），表示方法為『逆波蘭表示法』（Reverse Polish Notation, RPN）。

RPN 的意義在於，運算子永遠在運算元的後方，比方說：

• 3 + 4 會寫成 3 4 +
• (4 - 3) * 5 會寫成 4 3 - 5 *

這樣的好處在於不需要引入括號符號。

---

解題思路

堆疊 (Stack)

這種題型很明顯就是使用堆疊（stack）的資料結構來處理。我們每次在遇到數值時，就將其推入堆疊中；如果遇到運算符號，則彈出最頂部兩個數值進行運算。

到最後，堆疊只會剩下最後一個數值，該數值即是最終運算結果。

堆疊（Stack） 複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // Init
        stack<long> st;
        unordered_map<string, bool> opts({
            {"+", true},
            {"-", true},
            {"*", true},
            {"/", true},
        });

        for (auto& token: tokens) {
            if (opts[token]) {
                long a = st.top(); 
                st.pop();
                
                long b = st.top();
                st.pop();

                if (token == "+") {
                    st.push(b+a);
                }
                else if (token == "-") {
                    st.push(b-a);
                }
                else if (token == "*") {
                    st.push(b*a);
                }
                else if (token == "/") {
                    st.push(b/a);
                }
            }
            else {
                st.push(stol(token));
            }
        }

        return st.top();
    }
};

Python 範例程式碼

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        st = []
        for token in tokens:
            if token not in "+-*/":
                st.append(int(token))
            else:
                a = st.pop()
                b = st.pop()

                if token == "+":
                    st.append(b+a)
                elif token == "-":
                    st.append(b-a)
                elif token == "*":
                    st.append(b*a)
                elif token == "/":
                    st.append(b//a)
        
        return st[0]

---

References

• 150. Evaluate Reverse Polish Notation

---

Read More

• LeetCode 解題紀錄目錄