表达式求解中缀存为二叉树,后序遍历转为后缀,再解

《表达式求解中缀存为二叉树,后序遍历转为后缀,再解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、流程：将表达式(中缀)转化为二叉树，后序遍历该二叉树得到表达式的逆波兰表达式(后缀)，然后按照上一个实验计算即可计算如：8-(3+5)*(5-6/2)先按照优先级加上括号，得到：(8-((3+5)*(5-(6/2))))然后从最外层括号开始，依次转化成二叉树1、根是-，左子树8，右子树((3+5)*(5-(6/2)))2、右子树的根*，右子树的左子树(3+5)，右子树的右子树(5-(6/2))3、(3+5)的根+，左子树3，右子树54、(5-(6/2))的根-，左子树5，右子树(6/2)5、(6/2)的根/，左子树6，右子树2（用栈然后出

2、栈来实现构造子数，两个栈）再后序遍历该逆波兰表达式其中将中缀表达式转化为二叉树的算法是：设表达式类Express，树类Tree,由MakeNode(value)来生成值为value左右孩子为空的节点(叶子节点)voidM(Expressexp,Treet){if(exp为数或简单变量){t=MakeNode(exp);}elseif(exp形如"ex1opex2")//即op为二元操作符{t=MakeNode(op);M(ex1,t.LeftChild);M(ex2,t.RightChild);}elseif(exp形如"ex1op")/

3、/比如5!{t=MakeNode(op);M(ex1,t.RightChild);}}后序遍历二叉树的算法是：voidF(Treet){if(t==null){return;}F(t.LeftChild);F(t.RightChild);visit(t);//访问t}计算逆波兰表达式的算法：(用上一个实验的方法即可)设表达式记号tkn;操作数栈stk;while((tkn=GetNextToken())!=null){if(tkn==操作数){stk.push(tkn);continue;}elseif(tkn==操作符){a=stk.p

4、op();b=stk.pop();c=计算atknb;stk.push(c);continue;}}最后stk中剩余的操作数就是计算结果。法二：栈方法#include#includestructstack{chars[100];inttop;};structstacki{doubles[100];inttop;};voidpush(stack&s,chara){s.s[s.top++]=a;}charpop(stack&s){s.top--;returns.s[s.top];}intyouxian(c

5、hara,charb)//判断a的优先级是否比b高{if((b=='+'

6、

7、b=='-')&&(a=='*'

8、

9、a=='/'))return1;return0;}doublecount(doublea,doubleb,charc){switch(c){case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':returna/b;break;}}voidmain(){charzz[100];intkuoh[100],ktop;//运算符的在

10、括号的层数intlen,i,front;doublesum;stackstacks,stacky;stackijs;while(scanf("%s",zz)!=EOF){//中缀表达式到后缀表达式for(i=0;i<100;i++)kuoh[i]=0;stacks.top=stacky.top=ktop=0;len=strlen(zz);front=0;for(i=0;i

11、

12、zz[i]=='-'

13、

14、zz[i]=='*'

15、

16、zz[i]=='/'){push(stacky,zz[i]);kuoh[

17、ktop++]=front;}else{if(zz[i]!='('&&zz[i]!=')'){push(stacks,zz[i]);if(i=front&&youxian(zz[i+1],stacky.s[stacky.top-1])==0){push(stacks,pop(stacky));ktop--;}}}else{switch(zz[i]){case'(':front++;break;case')':while

18、(kuoh[ktop-1]==front){push(stacks,pop(stacky));ktop--;}front--;break;}}}}while(stacky.top!=0){pu