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

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