###### tags: `Leetcode` `medium` `stack` `python` `c++`

# 150. Evaluate Reverse Polish Notation

## [題目連結:https://leetcode.com/problems/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 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，遇到特殊符號再處理
* 題目要求 division between two integers should truncate toward zero. 向0取向
* python:
* int(float(val1)/val2)
* int(operator.truediv(int(val1), int(val2)))
* c++:
* 正常除法即可
* 對於c++:
* 由char轉成int
* 使用**stoi**(char) or **atoi**(char)
* 此題相乘若用一般int會報錯誤
* signed integer overflow
* 設long int解決

## Python:

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        operators={'+', '-', '*', '/'}
        stack=[]
        for char in tokens:
            #非數字
            if char not in operators:
                stack.append(int(char))
            else:
                val2=stack.pop()
                val1=stack.pop()
                if char=='+':
                    tmp=val1+val2
                elif char=='-':
                    tmp=val1-val2
                elif char=='*':
                    tmp=val1*val2
                else:
                    tmp=int(float(val1)/val2)
                    #int(operator.truediv(int(val1), int(val2)))
                stack.append(tmp)
        return stack[-1]

result = Solution()
tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
ans = result.evalRPN(tokens)
print(ans)

## C++:

#include<iostream>
#include<set>
#include<vector>
#include<stack>

using namespace std;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        set<string> operators{"+", "-", "*", "/"};
        stack<long int> res;
        for (auto item: tokens){
            if (operators.find(item)==operators.end())
                res.push(stoi(item));
            else{
                //一般的int 相乘會說signed integer overflow :"(
                long int val2=res.top(); res.pop();
                long int val1=res.top(); res.pop();
                if (item=="+")
                    val1+=val2;
                else if (item=="-")
                    val1-=val2;
                else if (item=="*")
                    val1*=val2;
                else
                    val1/=val2;
                res.push(val1);
            }
        }
        return res.top();
    }
};

int main(){
    vector<string> tokens{"2", "1", "+", "3", "*"};
    Solution res;
    int ans=res.evalRPN(tokens);
    cout<<ans<<endl;
    return 0;
}