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

流程：将表达式(中缀)转化为二叉树，后序遍历该二叉树得到表达式的逆波兰表达式(后缀)，然后按照上一个实验计算即可计算如：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 （用栈然后出栈来实现构造子数，两个栈）再后序遍历该逆波兰表达式其中将中缀表达式转化为二叉树的算法是：设表达式类Express，树类Tree, 由MakeNode(value)来生成值为value左右孩子为空的节点(叶子节点)void M(Express exp, Tree t)if(exp为数或简单变量)t = MakeNode(exp);else if(exp 形如ex1 op ex2)/即op为二元操作符t = MakeNode(op);M(ex1, t.LeftChild);M(ex2, t.RightChild);else if( exp 形如ex1 op)/比如5!t = MakeNode(op);M(ex1, t.RightChild);后序遍历二叉树的算法是：void F(Tree t)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;else if(tkn = 操作符)a=stk.pop(); b=stk.pop();c= 计算a tkn b;stk.push(c);continue;最后stk中剩余的操作数就是计算结果。法二：栈方法#include#includestruct stackchar s100;int top;struct stackidouble s100;int top;void push(stack &s,char a)s.ss.top+=a;char pop(stack &s)s.top-;return s.ss.top;int youxian(char a,char b)/判断a的优先级是否比b高if(b=+ | b=-) & (a=* | a=/)return 1;return 0;double count(double a,double b,char c)switch(c)case +:return a+b;break;case -:return a-b;break;case *:return a*b;break;case /:return a/b;break;void main()char zz100;int kuoh100,ktop;/运算符的在括号的层数int len,i,front;double sum;stack stacks,stacky;stacki js;while(scanf(%s,zz)!=EOF)/中缀表达式到后缀表达式for(i=0;i100;i+)kuohi=0;stacks.top=stacky.top=ktop=0;len=strlen(zz);front=0;for(i=0;ilen;i+)if(zzi=+ | zzi=- | zzi=* | zzi=/)push(stacky,zzi);kuohktop+=front;elseif(zzi!=( & zzi!=)push(stacks,zzi);if(i=front & youxian(zzi+1,stacky.sstacky.top-1)=0)push(stacks,pop(stacky);ktop-;elseswitch (zzi)case (:front+;break;case ):while(kuohktop-1=front)push(stacks,pop(stacky);ktop-;front-;break;while(stacky.top!=0)push(stacks,pop(stacky);for(i=0;istacks.top;i+)printf(%c,stacks.si);printf(n);/四则运算js.top=0;for(i=0;istacks.top;i+)if(stacks.si!=+ & stacks.si!=- & stacks.si!=* & stacks.si!=/)js.sjs.top+=stacks.si-0;elsesum=count(js.sjs.top-2,js.sjs.top-1,stacks.si);js.top-=2;js.sjs.top+=sum;printf(%lfn,sum);1。将后缀表达式转换为二叉树该方法是最简单的。如a + b*c 的后缀表达式为 bc*a+.处理步骤如下：（1）建立一个栈S （2）从左到右读后缀表达式，读到数字就创建叶子节点，节点值为数字值。将节点压入栈S中，读到运算符则创建中间节点，并从栈中依次弹出两个节点分别为Y和X，作为中间节点的左右子节点，然后以“X 运算符 Y”的形式计算机出中间节点的值，再将此中间节点压加栈S中（3）就重复第二步直至后缀表达式结束，此时栈顶的节点就是二叉树的根节点了。2。将中缀表达式转换为二叉树按照上一个回答者的方法: 将中缀表达式转换为后缀表达式的算法思想： 当读到数字直接送至输出队列中 当读到运算符t时， a.将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中； b.t进栈 读到左括号时总是将它压入栈中 读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号。 将中缀表达式转为后缀表达式，然后调用后缀表达式生成二叉树的解法即可。3。将前缀表达式转换为二叉树将前缀表达式直接取反即为后缀表达式。 如前缀表达式为+*bca，对应的后缀表达式为acb*+。因此，我们只需要字符串取反，然后调用后缀表达式的方法生成二叉树即可。( +中缀表达式转换为后缀表达式中缀转后缀是栈应用的一个典型例子。 其转换方法采用算府优先法。 转换过程需借助一个运算符栈和一个存放逆波兰表达式的数组。转换方法如下：将表达式开始符“ N” 压入运算符栈， 作为栈底元素。读入操作数， 直接存入数组。读入运算符， 压入运算符栈。 5 +若后进运算符优先级别高于当前栈顶元素时， 则继续进栈； =+若后进运算符优先级别低于或等于当前栈顶元素时， 则将当前栈顶元素出栈， 存入数组后