数据结构和算法java版本（9）中缀前缀后缀表达式原理_java 中缀转前缀和表达式算法

作者：Li_阴宅 | 2024-07-23 20:47:33

踩

java 中缀转前缀和表达式算法

数据结构和算法（9）中缀前缀后缀表达式

1）前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

2）例如：（2+4）*5-6对应的前缀表达式就是- * + 3 4 5 6

1.从右到左扫描表达式，遇到数字，将数字压入堆栈，遇到运算符，弹出栈顶的两个数，用运算符对他们做相应的计算（栈顶元素和次顶元素），并将结果入栈。

2.重复上述过程，知道表达式最左端，最后运算得出的值即为表达式的结果。

例如：（3+4）*5-6对应的前缀表达式是3 4 + 5 * 6 -，针对前缀缀表达式求值步骤如下：

1）从右至左扫描，将6、5、4、3压入堆栈

2）遇到+运算符，因此弹出3和4（3为栈顶元素，4位次顶元素），计算出3+4的值，得7，再将7入栈

3）接下来是 * 运算符，因此弹出7和5，计算出7*5=35，将35入栈

4）最后是-运算符，计算出35-6的值，即29，由此得出最终结果

1）中缀表达式就是常见的运算表达式，如（3+4）*5-6

2）中缀表达式的求值使我们最熟悉的，但是对计算机来说却不好操作，因此，在计算结果时，我们往往会将中缀表达式转换成其他表达式来操作（一般转成后缀表达式。）

1）后缀表达式又叫逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后，

2）中缀表达式举例说明：（3+4）*5-6对应的后缀表达式就是3 4 + 5 * 6 -

1.从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，（栈顶元素和次顶元素），并将结果入栈；

2.重复上述过程直到表达式最右端，最后运算出的值，即为表达式的结果

例如：（3+4）*5-6对应的后缀表达式是3 4 + 5 * 6 -，针对后缀表达式求值步骤如下：

1）从左至右扫描，将3和4压入堆栈

2）遇到+运算符，因此弹出4和3（4位栈顶元素，3位次顶元素），计算出3+4的值，得7；再将7入栈；

3）将5入栈

4）接下来是 * 运算符，因此弹出5和7，计算出7*5=35，将35入栈

5）将6入栈

6）最后是 - 运算符，计算出35-6的值，即29，由此得出最终结果

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/871417