逆波兰表达式求值＜难度系数＞

题述：根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意 两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例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 <= 10^4^
• tokens[i] 是一个算符（"+"、"-"、"*" 或 “/”），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

  中缀表达式面临的最大问题在于程序不方便运算，因为运算符优先级的问题，所以我们处理这种问题可以先将中缀表达式转换成后缀表达式，然后用后缀表达式进行运算。
  大概了解下中缀表达式转后缀表达式，这里需要借助栈

  

• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

🧷 平台：Visual studio 2017 && windows

核心思想：在了解完后缀表达式怎么由中缀表达式转换后，这里题目本意是需要我们计算后缀表达式的值。

leetcode原题

🧿 版本一

class Solution {public:    int evalRPN(vector<string>& tokens) {        stack<int> st;        for(const auto str : tokens)        {            //建议不要这样写,因为如果操作数是负数,就会出bug            /*switch(str[0]) { case: '+': //... ... }*/            int left, right;            //+、-、*、/,就出两个栈顶的元素,top1对应right,top2对应left,再把计算的结果入栈            if(str == "+")            {                right = st.top();                st.pop();                left = st.top();                st.pop();                st.push(left + right);            }            else if(str == "-")            {                right = st.top();                st.pop();                left = st.top();                st.pop();                st.push(left - right);            }            else if(str == "*")            {                right = st.top();                st.pop();                left = st.top();                st.pop();                st.push(left * right);            }            else if(str == "/")            {                right = st.top();                st.pop();                left = st.top();                st.pop();                st.push(left / right);            }            else//操作数            {                //入栈前,将字符串转整型                 st.push(stoi(str));            }        }        //返回此时栈顶的元素        return st.top();    }};

🧿 版本二 (优化版本一)

优化的点在于 “ 在判断操作符时有大量冗余的代码 ”。

解决方案：

1. 封装一个成员函数 (能解决，但还能更好的方法 ？)。
2. 这道题使用 map 非常简单，但目前我们还没学，就不谈了。
3. 使用逻辑或 “ || ”，这种写法的问题是把运算结果 push 时不知道是什么操作符。解决方法就是定义一个 48 大小的数组建立映射关系，比如在下标 47 的位置存储 “ / ”，然后根据对应的字符就可以取到对应的符号，但是数组里所存储的字符，不是类型，所以没错，~~ 翻车了，连第 2 种方案好像也翻车了，所以这里给成员函数好像是比较好的方案了，或者在 “ || ” 的基础上使用 switch 语句 (这两种方法差不多，只是减少了代码量，本质并没有多少的改进)。无妨，多翻车才能更好的上车嘛 ！！！
   注：其实也有更好的简化的方案的，只不过目前我们玩不了，这里先吊下大家的胃口 —— C++11 的包装器。也欢迎大家有更好的方案可以在评论区留言。

//版本二(优化版本一)class Solution {public:    //解决方案一：    void getnum(stack<int>& st, int& l, int& r)    {}    int evalRPN(vector<string>& tokens) {        stack<int> st;        for(const auto str : tokens)        {            int left, right;            if(str == "+" || str == "-" || str == "*" || str == "/")            {                right = st.top();                st.pop();                left = st.top();                st.pop();                switch(str[0])                {                case '+':                    st.push(left + right);                    break;                case '-':                    st.push(left - right);                    break;                case '*':                    st.push(left * right);                    break;                case '/':                    st.push(left / right);                    break;                }            }            else            {                st.push(stoi(str));            }        }        return st.top();    }};

🧿 版本三 (优化版本二，骚操作)

这里可以先跳过，把后面 C++11 的包装器、map 等，等学了再来看。

class Solution {public:    int evalRPN(vector<string>& tokens) {        map<string, function<int(int, int)>> opCountMap =         {            {"+", [](int x, int y)->int{return x + y;}},            {"-", [](int x, int y)->int{return x - y;}},            {"*", [](int x, int y)->int{return x * y;}},            {"/", [](int x, int y)->int{return x / y;}}        };                stack<int> st;        for(auto& str : tokens)        {            if(str == "+" || str == "-" || str == "*" || str == "/")            {                int right = st.top();                st.pop();                int left = st.top();                st.pop();                st.push(opCountMap[str] (left, right));            }            else            {                st.push(stoi(str));            }        }        return st.top();    }};