LeetCode 150. Evaluate Reverse Polish Notation [Medium] [C++] 解題筆記

 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

想法:

    看到這類要做四則運算或是判斷括弧是否正確的題目用 stack 就對拉！，這題的程式碼應該很簡單明瞭，就直接

看code吧。

完整程式碼:

/* Stack , O(n) time, O(n) space */
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> s;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int op1 = s.back();
                s.pop_back();
                int op2 = s.back();
                s.pop_back();
                if (tokens[i] == "+") { s.push_back(op2 + op1); }
                if (tokens[i] == "-") { s.push_back(op2 - op1); }
                if (tokens[i] == "*") { s.push_back(op2 * op1); }
                if (tokens[i] == "/") { s.push_back(op2 / op1); }
            }
            else {
                s.push_back(stoi(tokens[i]));
            }
        }
        return s.back();       
    }
};