LeetCode150-ReversePolishexpressionevaluationEvaluateReversePolishNotation

题目：根据逆波兰表示法求出表达式的值。有效的运算符包括+、-、*、/。每个操作数可以是整数或另一个反向波兰表达式。计算反向波兰表示法中算术表达式的值。有效的运算符是+、-、*、/。每个操作数可以是一个整数或另一个表达式。注意：整数除法只保留整数部分。给定的反波兰表达式总是有效的。换句话说，表达式将始终产生有效值，并且不存在除以0的数。注意：两个整数之间的除法应截断为零。给定的RPN表达式总是有效的。这意味着表达式将始终计算结果并且不会有任何被零除的操作。示例1：输入：["2","1","+","3","*"]输出：9解释：((2+1)*3)=9示例2：输入：["4","13","5","/","+"]输出：6解释：(4+(13/5))=6示例3：输入：["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扩展：反波兰表达式，其文法规定表达式必须是以逆波兰表达式的形式给出。反波兰表达式也称为后缀表达式。这个知识点在数据结构和编译原理两门课程中都有介绍。这里有一些例子：a+b--->a,b,+a+(b-c)--->a,b,c,-,+a+(b-c)*d--->a,b,c,-,d,*,+a+d*(b-c)--->a,d,b,c,-,*,+a=1+3--->a,1,3,+,=它从上面的例子可以看出：(1)在两种表示中，操作数的出现顺序是一样的；(2)在后缀表示中，运算符按照实际计算顺序从左到右排列，每个运算符后面总是跟着它的操作数。这个表达方式很反人类，但是对计算机却很友好，因为计算机操作使用的是栈数据结构。解题思路：可以看出，逆波兰表达式中的每个运算符都属于该运算符之前的两个数之间的运算。例如：如波兰语表达：1,2,+，加号前的两个数字是1,2。它的运算符是加号：1+2得出结果：1+2=3如波兰语表达式：1,2,3,+,-那么加号前的两个数就是2,3。它的运算符是加号：2+3给出结果2+3=5，那么波兰语表达式就变成了：1,5,-减号前的两个数是1,5，它的运算符是减号：1-5得到结果1-5=-4从上面的例子来看，思路很清晰了。直接用指针遍历表达式，遇到数字就入栈。当它遇到操作员时，会弹出两个数字。他们计算后得到结果，然后作为一个独立的数压入栈中。最后栈中只剩下一个元素，就是表达式运算的结果。也可以使用递归Java：classSolution{publicintevalRPN(String[]tokens){Stackstack=newStack<>();for(Stringt:tokens){if(t.equals("+")){stack.push(stack.pop()+stack.pop());}elseif(t.equals("-")){inttmp=stack.pop();stack.push(stack.pop()-tmp);}elseif(t.equals("*")){inttmp=stack.pop();stack.push(stack.pop()*tmp);}elseif(t.equals("/")){inttmp=stack.pop();stack.push(stack.pop()/tmp);}else{stack.push(Integer.parseInt(t));}}返回stack.pop();}}Python：Python也可以用数组代替栈来完成上面的方法来回答这个问题。这里用另外一个函数eval()代替上面的四个if判断：classSolution:defevalRPN(self,tokens:List[str])->int:stack=[]fortintokens:iftin'+-*/':tmp=stack.pop()stack.append(int(eval('stack.pop()'+t+'tmp')))else:stack.append(int(t))returnstack.pop()eval()函数可以执行传入参数字符串的语句。比如eval('print("hhhhh")')会执行参数字符串，打印出hhhhh欢迎大家关注微信。新工。公众号：爱写Bug