当前位置:网站首页>后缀表达式转中缀表达式

后缀表达式转中缀表达式

2020-11-08 18:11:44 修罗神·唐三

假定有后缀表达式1 2 3 + 4 * +5 – ,请将它转化为前缀表达式。

利用表达式树:

    1.从左到右扫面后缀表达式,一次一个符号读入表达式。

    2.如果符号是操作数,那么就建立一个单节点树并将它推入栈中。如果符号是操作符,那么就从栈中弹出两个树T1和T2(T1先弹出)并形成一颗新的树,该树的根就是操作符,

       它的左、右儿子分别是T2和T1(先出的为右子树,后出的为左子树)。然后将指向这棵新树的指针压入栈中。

 

 

 

前三个符号是操作数,因此创建三颗单节点树并将指向它们的指针压入栈中

 

 “+”被读入,因此指向最后两颗树的指针被弹出,形成一颗新树,并将指向新树的指针压入栈中。

 

 

     扫描4和*后

 

 

扫描+和5后

扫描-后

版权声明
本文为[修罗神·唐三]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/pxy071128fzm/p/13945054.html