LeetCode150_Evaluate Reverse Polish Notation评估逆波兰表达式（栈相关问题）

题目：

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are+,-,*,/. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

理解这道题首先要理解什么是波兰表达式、什么是逆波兰表达式，这个表达式的意义何在：看参考链接；

参考链接：

Evaluate Reverse Polish Notation：https://www.cnblogs.com/dolphin0520/p/3708587.html

波兰式、逆波兰式与表达式求值：https://blog.csdn.net/linraise/article/details/20459751

思路：

　　我们熟悉的带括号的表达式，叫做中缀表达式，符合人们的直观感受。但是对于计算机来说，开销较大。

　　波兰表达式（后缀表达式）的意义在于不需要使用括号来决定哪个运算先运行，利用栈的特性来模拟计算，遍历这个逆波兰表达式数组，遇到操作数推进操作数的栈s；遇到操作符，将栈s顶两个操作数a和b取出进行操作符运算，最后将运算结果c放进栈中。

代码实现：

 1 class Solution {
 2 public:
 3     int evalRPN(vector<string>& tokens) 
 4     {
 5         stack<int> sk;
 6         for(int i = 0; i<tokens.size();i++)
 7         {
 8             if( tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/" )
 9             {
10                 if(sk.size()<2)
11                     return 0;
12                 int op1 = sk.top(); sk.pop();
13                 int op2 = sk.top(); sk.pop();
14                 int res = 0;
15                 
16                 if(tokens[i] == "+")
17                     res = op1+op2;
18                 if(tokens[i] == "-")
19                     res = op2-op1;                
20                 if(tokens[i] == "*")
21                     res = op1*op2;
22                 if(tokens[i] == "/")
23                     res = op2/op1;
24                 
25                 sk.push(res);
26             }
27             else
28 
29                 sk.push(stoi(tokens[i]));               
30         }
31         return sk.top();
32    }
33         
34 };