150. 逆波蘭表達式求值
給你一個字符串數組 tokens ，表示一個根據 逆波蘭表示法 表示的算術表達式。
請你計算該表達式。返回一個表示表達式值的整數。
注意：
有效的算符為 '+'、'-'、'*' 和 '/' 。
每個操作數（運算對象）都可以是一個整數或者另一個表達式。
兩個整數之間的除法總是 向零截斷 。
表達式中不含除零運算。
輸入是一個根據逆波蘭表示法表示的算術表達式。
答案及所有中間計算結果可以用 32 位 整數表示。
?
示例 1：
輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9
示例 2：
輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6
示例 3：
輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22
解釋：該算式轉化為常見的中綴算術表達式為：
? ((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
?
提示：
1 <= tokens.length <= 104
tokens[i] 是一個算符（"+"、"-"、"*" 或 "/"），或是在范圍 [-200, 200] 內的一個整數
?
逆波蘭表達式：
逆波蘭表達式是一種后綴表達式，所謂后綴就是指算符寫在后面。
平常使用的算式則是一種中綴表達式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
該算式的逆波蘭表達式寫法為 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波蘭表達式主要有以下兩個優(yōu)點：
去掉括號后表達式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據次序計算出正確結果。
適合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，并將結果壓入棧中
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/evaluate-reverse-polish-notation
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。
波蘭表達式：
就是將表達式表示成二叉樹然后通過后續(xù)遍歷表達出來，
通過利用棧可以將其結果計算出來
第一種對法：
class?Solution?{
public:
????int?evalRPN(vector<string>&?tokens)?{
????????stack<long?long>?s;
????????for(int?i=0;i<tokens.size();i++){
????????????if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
????????????????long?long?a?=?s.top();s.pop();
????????????????long?long?b?=?s.top();s.pop();
????????????????long?long?temp=0;
????????????????if(tokens[i]=="+"){
????????????????????temp?=?a?+?b;?
????????????????????s.push(temp);
????????????????}else?if(tokens[i]=="-"){
????????????????????temp?=?b?-?a;
????????????????????s.push(temp);
????????????????}else?if(tokens[i]=="*"){
????????????????????temp?=?a?*?b;
????????????????????s.push(temp);
????????????????}else?if(tokens[i]=="/"){
????????????????????temp?=?b?/?a;
????????????????????s.push(temp);
????????????????}
????????????}else{
????????????????s.push(stoll(tokens[i]));
????????????}
????????}
????????return?s.top();
????}
};
注意：因為是后續(xù)遍歷出來的字符串，所以因該是第二個作被除數，第一個作除數，
第二個作被減數，第一個作減數
