题目

逆波兰表达式

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) ) 。
逆波兰表达式主要有以下两个优点：

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

  思路

  其实这道题算简单，因为题目给了RPN的定义，所有根据理解用栈就可以实现了。

  大佬解答

  逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。
  但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化了，就可以了

  中缀与后缀表达式

  我们习惯看到的表达式都是中缀表达式，因为符合我们的习惯，但是中缀表达式对于计算机来说就不是很友好了。
  例如：4 + 13 / 5，这就是中缀表达式，计算机从左到右去扫描的话，扫到13，还要判断13后面是什么运算法，还要比较一下优先级，然后13还和后面的5做运算，做完运算之后，还要向前回退到 4 的位置，继续做加法。
  那么将中缀表达式，转化为后缀表达式之后：[“4”, “13”, “5”, “/“, “+”] ，就不一样了，计算机可以利用栈里顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的。
  可以说本题不仅仅是一道好题，也展现出计算机的思考方式。

Code

c++中，数字字符转Int

使用stoi()字符处理函数，把数字字符串转换成int输出

atoi()与stoi()区别：

相同点：

• 都是C++的字符处理函数，把数字字符串转换成int输出
• 头文件都是#include

不同点：

• atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char*类型的。
• atoi()不会做范围检查，如果超出范围的话，超出上界，则输出上界，超出下界，则输出下界
• stoi()的参数是const string&,不需要转化为 const char*。

• stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error！

  class Solution {
  public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0;i<tokens.size();i++){
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                //是运算符
               int tempr =st.top();
               st.pop();
               int templ =st.top();
               st.pop();
               int result;
               if(tokens[i]=="+"){
                   result =templ+tempr;
               }else if(tokens[i]=="-"){
                   result =templ-tempr;
               }else if(tokens[i]=="*"){
                   result =templ*tempr;
               }else{
                   result =templ/tempr;
               }
                st.push(result);
            }else{
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
    }
  };