# Leetcode [No. 150] Evaluate Reverse Polish Notation

## 題目

https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

## 思路
+ 這個題目是資料結構常常會出現的題目，通常會在教stack的時候一起出
+ 簡單來說就是把operator放在後面，希望你活用stack特性去解決
+ 我的做法就是如果今天是數字，我就把它放到stack裡面
+ 如果不是的話我就把stack裡面的數字拿出來運算

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for(int i = 0 ; i < tokens.size(); i++)
        {
            if(tokens[i] == "+")
            {
                int second = s.top();
                s.pop();
                int first = s.top();
                s.pop();
                s.push(first + second);
            }
            else if (tokens[i] == "-")
            {
                int second = s.top();
                s.pop();
                int first = s.top();
                s.pop();
                s.push(first - second);
            } 
            else if (tokens[i] == "*")
            {
                int second = s.top();
                s.pop();
                int first = s.top();
                s.pop();
                s.push(first * second);
            } 
            else if (tokens[i] == "/")
            {
                int second = s.top();
                s.pop();
                int first = s.top();
                s.pop();
                s.push(first / second);
            } 
            else 
            {
                s.push(stoi(tokens[i]));
            }             
        }
        return s.top();
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

## 改良

class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> stk;
        int res = 0;
        for(auto token : tokens) { 
            if(token == "+" || token == "-" || token == "*" || token == "/") {
                if (stk.size() < 2) {
                    return false;
                } else {
                    int topValue = stk.top();
                    stk.pop();
                    if (token == "+") {
                        topValue = stk.top() + topValue;
                    } else if (token == "-") {
                        topValue = stk.top() - topValue;
                    } else if (token == "*") {
                        topValue = stk.top() * topValue;
                    } else if (token == "/") {
                        topValue = stk.top() / topValue;
                    } 
                    stk.pop();
                    stk.push(topValue);
                }
            } else {
                stk.push(stoi(token));
            }
        }
        return stk.top();
    }
};