Man cannot live like a beast, he should pursue knowledge and virtue. -- Dante
1. 题目描述
2. 题目分析与解析
2.1 思路一
这个波兰式我记得在之前上编译原理的时候学过，是对输入的代码进行解析用的。可能有一部分读者对于波兰表达式并不太熟悉，我按照题目给的一个例子来解释一下：
比如对于上述测试用例，遍历tokens，发现2，说明它是一个操作数，继续向后走，发现1，说明是另一个操作数，然后发现 +，说明此时需要进行 2+1的操作，这个结果 =3，它又相当于一个操作数。
继续向后，发现3，当作第二个操作数，然后发现 *，进行运算，将结果又当作一个操作数。但是因为已经没有后续运算了，所以 3*3=9，9就是结果输出。
其实经过一个测试用例，应该就能很快想到使用栈来解决。因为每发现一个运算符号，就说明就要对前面的操作数进行运算了，就相当于入栈时发现入栈的元素是运算符号，就弹出两个运算数进行运算，并将新的运算结果放入栈作为一个新的运算数。
当然题目提示了：
如果没有提示该内容，我们还需要考虑各种运算优先符，比如：(),[],{}，对于这种情况就需要对左右括号进行匹配，然后取出内部内容进行运算，我们这里就不考虑了。
代码思路：
-
定义一个栈，用来存储运算
-
遍历tokens
-
当发现当前入栈元素为数字，就入栈
-
当发现当前入栈元素是操作符，就取出两个栈中的操作数进行运算，并将运算结果放入栈
-
-
遍历结束，栈顶元素就是结果
虽然能accept，但是效果并不好
（最后看了下官方，发现思路没什么问题，但是在判断是否为数字的过程我本来使用的是正则表达式：
tokens[i].matches("-?\\d+")
获得上述效果，但是官方用的是：
因为这个原因导致了判定是否数字可能效率很低，如果上述思路也使用isNumber能获得如下结果：
)
2.2 思路二
下面一种方法是对于栈空间的优化，引自力扣官方，可以看看：
后面3.2贴上带解析的代码。
3. 代码实现
3.1 思路一
3.2 思路二
4. 相关复杂度分析
分析时间复杂度：
-
evalRPN方法：
-
时间复杂度：O(n)，其中 n 为 tokens 数组的长度。因为需要遍历 tokens 数组，对于每个元素进行入栈、出栈或运算操作，都是常数时间复杂度的操作。
-
-
evalRPN方法（使用isNumber）：
-
时间复杂度：同样是 O(n)，因为整体操作与 evalRPN 方法相同，只是在判断是否为数字时，使用了自定义的 isNumber 方法，但这并不改变时间复杂度。
-
-
evalRPN3方法：
-
时间复杂度：同样是 O(n)，因为整体操作与 evalRPN 方法相似，但是使用了数组模拟栈，数组的大小为 (n + 1) / 2，而且每个元素只入栈或出栈一次，所以时间复杂度与 evalRPN 方法相同，都是线性时间复杂度。
-
分析空间复杂度：
-
evalRPN方法：
-
空间复杂度：O(n)，主要是由栈的空间消耗决定的，栈的最大空间不超过 n/2 + 1，但因为其他常数因素，可以简化为 O(n)。
-
-
evalRPN方法（使用isNumber）：
-
空间复杂度：与 evalRPN 方法相同，仍然是 O(n)。
-
-
evalRPN3方法：
-
空间复杂度：这里使用数组模拟栈，数组的大小为 (n + 1) / 2，因此空间复杂度为 O(n)。
-
综上所述，三种方法的时间复杂度都是 O(n)，空间复杂度也都是 O(n)，其中 n 为 tokens 数组的长度。
