word怎么做网站链接,网站开发设计过程,电脑网站网页设计,怎么可以预览自己做的网站Man cannot live like a beast, he should pursue knowledge and virtue. -- Dante 1. 题目描述 2. 题目分析与解析
2.1 思路一
这个波兰式我记得在之前上编译原理的时候学过#xff0c;是对输入的代码进行解析用的。可能有一部分读者对于波兰表达式并不太熟悉#xff0c;…Man cannot live like a beast, he should pursue knowledge and virtue. -- Dante 1. 题目描述 2. 题目分析与解析
2.1 思路一
这个波兰式我记得在之前上编译原理的时候学过是对输入的代码进行解析用的。可能有一部分读者对于波兰表达式并不太熟悉我按照题目给的一个例子来解释一下 比如对于上述测试用例遍历tokens发现2说明它是一个操作数继续向后走发现1说明是另一个操作数然后发现 说明此时需要进行 21的操作这个结果 3它又相当于一个操作数。
继续向后发现3当作第二个操作数然后发现 *进行运算将结果又当作一个操作数。但是因为已经没有后续运算了所以 3*399就是结果输出。
其实经过一个测试用例应该就能很快想到使用栈来解决。因为每发现一个运算符号就说明就要对前面的操作数进行运算了就相当于入栈时发现入栈的元素是运算符号就弹出两个运算数进行运算并将新的运算结果放入栈作为一个新的运算数。
当然题目提示了 如果没有提示该内容我们还需要考虑各种运算优先符比如(),[],{}对于这种情况就需要对左右括号进行匹配然后取出内部内容进行运算我们这里就不考虑了。
代码思路 定义一个栈用来存储运算 遍历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 数组的长度。
