逆波兰表达式求值的思路探讨与源码
逆波兰表达式求值的题目如下图，该题属于栈和数组类型的题目，主要考察对于栈的使用和栈结构原理的理解。本文的题目作者想到2种方法，分别是数组模拟栈方法和列表模拟方法，其中数组模拟栈方法使用Java进行编写，而列表模拟方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。
本人认为该题目可以使用数组模拟栈的思路进行解决，首先初始化下标的值并计算输入的字符串数组的长度，并且初始化一个和输入字符串数组长度一样的数组。然后开始遍历字符串数组，从加减乘除四个情况去考虑，如果是加法的情况，那就把数组的当前下标对应的值和前一个下标对应的值加起来并赋值给当前的值；如果是乘法的情况，处理和加法一样，只是最后把下标对应的值乘起来并赋值给当前的值；如果是减法的情况就要取当前下标对应的元素减去前一个下标对应的元素的结果再赋值给当前下标对应的元素；如果是除法的情况也和减法的操作类似，只是最后是把除法的结果赋值给当前元素的值。如果不是加减乘除的情况，那么就是数字，这种情况就直接进行类型转换后赋值给数组的下一个元素对应的值。最后遍历结束并返回下标所对应的数组的值就最终结果。那么按照这个思路我们的Java代码如下：
#喷火龙与水箭龟class Solution {public int evalRPN(String[] tokens) {int ind = -1; int tokenLen = tokens.length;int[] arr = new int[tokenLen];for (String str:tokens) {if (str.equals("+")) {int a = arr[ind--];int b = arr[ind];arr[ind] = a + b;} else if (str.equals("*")) {int a = arr[ind--];int b = arr[ind];arr[ind] = b * a;} else if (str.equals("-")) {int a = arr[ind--];int b = arr[ind];arr[ind] = b - a;} else if (str.equals("/")) {int a = arr[ind--];int b = arr[ind];arr[ind] = b / a;} else {arr[++ind] = Integer.valueOf(str);}}return arr[ind];}}
显然，我们看到数组模拟栈算法的效果还行，同时还可以使用列表模拟的方法解决。首先初始化一个空列表，然后开始遍历字符串数组，如果是加号，那就从列表的尾部弹出一个值后再弹出一个值，把两个值相加得到的结果插入列表尾部；如果是乘号，那就是把依次弹出的两个值进行相乘以后再插入到列表尾部；如果是减号，那就把后弹出的那个元素减去先弹出的那个元素并插入到列表尾部；如果是除号，那就把后弹出的那个元素除以先弹出的那个元素并插入到列表尾部。如果不是加减乘除的情况那就直接把结果插入到列表尾部。最终返回列表尾部的值其实就是最终的求值结果。其实这种思路就是用列表去模拟进栈和出栈的操作，所以按照这个思路就可以解决，下面是Python代码：
#喷火龙与水箭龟class Solution: def evalRPN(self, tokens: List[str]) -> int: arr = [] for jr in tokens: if(jr=='+'): arr.append(arr.pop()+arr.pop()) elif(jr=='*'): arr.append(arr.pop()*arr.pop()) elif(jr=='-'): arr.append((-1)*arr.pop()+arr.pop()) elif(jr=='/'): arr.append(int(1/arr.pop()*arr.pop())) else: arr.append(int(jr)) return arr.pop()
从结果来说Java版本的数组模拟栈方法的效率还不错，而Python版本的列表模拟方法的速度也还可以，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。