当前位置:   article > 正文

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

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 -

正常的表达式逆波兰表达式
a+ba b +
a+(b-c)a b c - +
a+(b-c)*da b c - d * +
a+d*(b-c)+a d b c - * +
a=1+3a 1 3 + =

后缀表达式的计算机求值原理

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
推荐阅读
相关标签
  

闽ICP备14008679号