题目：

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放进栈中。

代码实现：

 class Solution {

 public:

     int evalRPN(vector<string>& tokens)

     {

         stack<int> sk;

         for(int i = ; i<tokens.size();i++)

         {

             if( tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/" )

             {

                 if(sk.size()<)

                     return ;

                 int op1 = sk.top(); sk.pop();

                 int op2 = sk.top(); sk.pop();

                 int res = ;

                 if(tokens[i] == "+")

                     res = op1+op2;

                 if(tokens[i] == "-")

                     res = op2-op1;

                 if(tokens[i] == "*")

                     res = op1*op2;

                 if(tokens[i] == "/")

                     res = op2/op1;

                 sk.push(res);

             }

             else

                 sk.push(stoi(tokens[i]));

         }

         return sk.top();

    }

 };

巴特西

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

参考链接：

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

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

最新文章

热门文章