逆波兰表达式求值(栈)

向右看齐 2023-10-10 23:35 35阅读 0赞

一、逆波兰表示法

逆波兰表达式又叫做[后缀表达式][Link 1]。逆波兰表示法是波兰[逻辑学家][Link 2]J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 \[1\]  。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

中缀表达式：就是我们平时用的表达式，比如 1+((2+3)\*4)-5这种表达式

比如：“1+((2+3)\*4)-5”转换为后缀表达式是”1 2 3 + 4 \* + 5 -”，可以发现后缀表达式里没有括号。

具体可以用这样的方法转换：

这里我们先把中缀表达式写为这样：（（1+（（2 + 3）\*4））-5）在表达式里每一步运算都加上括号，颜色相同的括号相对应

![edb2821b0bf343129b1860e19b170eb3.png][]

然后我们将对应的操作符（运算符）挪到对应的括号后面，如下：

![fb375eae74b846b5a826e75c0e58dca4.png][]

然后我们去掉括号就得到了后缀表达式：1 2 3 + 4 \* + 5 -

[150. 逆波兰表达式求值 - 力扣（LeetCode）][150. _ - _LeetCode]

我们以此题为例

![be35cdb8bff9494d8950789b08e3b501.png][]

我们首先创建一个evalRPN方法 并创建一个栈 ![37300efb3a0040b4aff260eb467fc886.png][]

然后我们用for each 方法去遍历这个字符型数组 此时我们需要判断所遍历的字符是否为有效的算符 所以我们创建一个 isOperation方法来进行判断 如果是返回ture 不是则返回false,此时比较两个类型我们用equals方法 更为合适

![1d8f8465cf094b31b03189c86045aeeb.png][]

此时如果我们遍历的符号不是有效运算符的话那我们需要将他插入栈中 但是此时我们的x是string类型 所以我们需要用Interger.setInt(x)进行转换

然后如果我们遍历的符号是有效的运算符的话 ,根据我们最开始的了解对后缀表达式进行运算我们设置num1,num2来存储从栈取出来的值 我们设置num2为运算符号右边的数值,因为栈是先进后出的, 所以我们先取出num2的值,再取出num1的值. 然后我们用swith语句进行判断 该x为哪个有效字符 并进行相应的运算,并将这个运算值插入栈中 继续运算(此时需要注意的是num1-num2的顺序不能变)

![cd61fdeb4d564c16841073d407cfb24d.png][]

经过以上的代码我们已经完成运算 , 因为运算完会将值插入栈中,所以最后我们返回stack.pop.

![4c24bd8f04a440d69b7bb83317f26053.png][]

[Link 1]: https://baike.baidu.com/item/%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/6160580?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E9%80%BB%E8%BE%91%E5%AD%A6%E5%AE%B6/1240880?fromModule=lemma_inlink
[edb2821b0bf343129b1860e19b170eb3.png]: https://img-blog.csdnimg.cn/edb2821b0bf343129b1860e19b170eb3.png
[fb375eae74b846b5a826e75c0e58dca4.png]: https://img-blog.csdnimg.cn/fb375eae74b846b5a826e75c0e58dca4.png
[150. _ - _LeetCode]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/submissions/
[be35cdb8bff9494d8950789b08e3b501.png]: https://img-blog.csdnimg.cn/be35cdb8bff9494d8950789b08e3b501.png
[37300efb3a0040b4aff260eb467fc886.png]: https://img-blog.csdnimg.cn/37300efb3a0040b4aff260eb467fc886.png
[1d8f8465cf094b31b03189c86045aeeb.png]: https://img-blog.csdnimg.cn/1d8f8465cf094b31b03189c86045aeeb.png
[cd61fdeb4d564c16841073d407cfb24d.png]: https://img-blog.csdnimg.cn/cd61fdeb4d564c16841073d407cfb24d.png
[4c24bd8f04a440d69b7bb83317f26053.png]: https://img-blog.csdnimg.cn/4c24bd8f04a440d69b7bb83317f26053.png