【LeetCode】 150. Evaluate Reverse Polish Notation

Description

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:

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

Solution

• 基本上就是後敘表達的題目，沒學過的可以參考這邊
• 簡單來說就是用一個 Stack 把"數字"存起來
• 如果遇到運算，就把 Stack 最後兩個拿出來做計算，算完放回 Stack
• 最後每個 token 都跑完之後，留在 Stack 的元素就會是答案了
• 好像可以寫得乾淨一點，不過算了
  • 要注意 temp1 和 temp2 在 - 和 / 會有順序的差異。

Code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> numStack;
        int temp1, temp2;
        for(int i = 0; i < tokens.size(); i++)
        {
            if(tokens[i] == "+")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp1 + temp2);
            }
            else if(tokens[i] == "-")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp2 - temp1);
            }
            else if(tokens[i] == "*")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp1 * temp2);
            }
            else if(tokens[i] == "/")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp2 / temp1);
            }
            else
                numStack.push_back(stoi(tokens[i]));
        }
        return numStack.back();
    }
};

tags: LeetCode C++