资源描述
1问题描述（1）表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式，女口：11+22*（7-4）/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：2274-*3/11+）和前缀式（如：+11/*22743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2数据结构设计（1）表达式求值问题由于表达式中有字符与数字两种类型，故定义结点一个标志域data，标志结点存储的为字符data=2还是数字data=1,再寻找结点中对应的存储位置，读取数字域data1，字符域data2。而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。typedefstructNode定义存储中缀表达式的结点类型intdata;intdata1;chardata2;structNode*next;Lnode;typedefstructNode2定义存储前缀表达式的结点类型intdata;intdata1;chardata2;structNode2*next;structNode2*prior;Lnode2;3运行、测试与分析（1）表达式求值问题（1）按提示输入中缀表达式，如图1.1所示。如输入中缀表达式不正确，提示输入有误，如图1.2,1.3所示。图nIC:UsersAdninistritorXDesktcpDebugUntitledl.exe遺输中墾義莖垂牡卄畑玷输/k中缀表达式有误Pfeswanyheytccontinue图12丄丄(2) 选择表达式转换并求值方式。按“1”选择中缀表达式求值，如图1.4所示。图1.4(3) 按“2”选择中缀表达式转变为后缀表达式并求值，如图1.5所示。图1.5(4) 按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示。C:U5er5Administr3torDE5ktcpD?tugUnti:ledl.exe输人血达式输人诟缀表达式求值，输入2前缀表达式求恒日+12/-*34563411=182PressanykeytoCDntinue图1.6()表达式求值问题#includevstdio.h#includevstdlib.h#defineMAXNUM100typedefstructNode定义存储中缀表达式的结点类型intdata;intdatal;chardata2;structNode*next;Lnode;typedefstructNode2定义存储前缀表达式的结点类型intdata;intdata1;chardata2;structNode2*next;structNode2*prior;Lnode2;typedefintselemtype1;定义运算数栈的结点typedefstruct定义运算数栈的类型selemtype1*base;selemtype1*top;sqstack1;voidInitStack1(sqstack1&s)新建一个空运算数栈s.base=(selemtype1*)malloc(MAXNUM*sizeof(selemtype1);s.top=s.base;if(!s.base)printf(出错：申请空间失败！n);voidPushl(sqstackl&s,selemtypel&e)运算数栈，入栈：插入元素e为新的栈顶元素if(s.top-s.base=MAXNUM)printf(出错：表达式过长！1n);*s.top+=e;voidGetTop1(sqstack1s,selemtype1&e)运算数栈，用e返回栈顶元素e=*(s.top-1);voidPopopnd1(sqstack1&s,selemtype1&e)运算数栈，退栈：删除栈顶元素，并用e返回其值e=*-s.top;intstackempy1(sqstack1s)运算数栈，若为空栈返回1,否则返回0if(s.top=s.base)return1;elsereturn0;typedefcharselemtype2;定义运算符栈的结点类型typedefstruct定义运算符栈类型selemtype2*base;selemtype2*top;sqstack2;voidInitStack2(sqstack2&s)新建一个空运算符栈s.base=(selemtype2*)malloc(MAXNUM*sizeof(selemtype2);s.top=s.base;if(!s.base)printf(出错：申请空间失败！n);voidPush2(sqstack2&s,selemtype2&e)运算符栈，入栈：插入元素e为新的栈顶元素if(s.top-s.base=MAXNUM)printf(出错：表达式过长！2n);*s.top+=e;voidGetTop2(sqstack2s,selemtype2&e)运算符栈，用e返回栈顶元素e=*(s.top-l);voidPopopnd2(sqstack2&s,selemtype2&e)运算符栈，退栈：删除栈顶元素，并用e返回其值e=*-s.top;intstackempy2(sqstack2s)运算符栈，若为空栈返回1,否则返回0if(s.top=s.base)return1;elsereturn0;voidpriority(charc,int&i)确定运算符优先级if(c=*llc=7llc=%)i=2;else讦(c=+llc=-)i=1;elsei=0;intcompare(chara,charb)比较栈顶元素运算符与外部运算符优先级大小，外部优先级大则返回1,反之返回0intin,out;priority(a,in);priority(b,out);if(outin)return1;elsereturn0;voidOperat(sqstack1&OPND,sqstack2&OPTR)intnum1,num2,num;charc;Popopnd1(OPND,num2);Popopnd1(OPND,num1);Popopnd2(OPTR,c);switch(c)case+:num=num1+num2;break;case-:num=num1-num2;break;case*:num=num1*num2;break;case7:num=num1/num2;break;case%:num=num1%num2;break;Push1(OPND,num);voidOperatqianzhui(sqstackl&OPND,sqstack2&OPTR)intnum1,num2,num;charc;Popopnd1(OPND,num1);Popopnd1(OPND,num2);Popopnd2(OPTR,c);switch(c)case+:num=num1+num2;break;case-:num=num1-num2;break;case*:num=num1*num2;break;case7:num=num1/num2;break;case%:num=num1%num2;break;Push1(OPND,num);后缀表达式求值voidhouzhuiqiuzhi(Lnode*p,int&e)sqstack1OPND;运算数栈sqstack2OPTR;运算符栈intn;charc;p=p_next;InitStack1(OPND);InitStack2(OPTR);while(p)case1:n=p-data1;switch(p-data)Pushl(OPND,n);break;case2:c=p-data2;Push2(0PTR,c);Operat(OPND,OPTR);break;default:printf(”结点有误)；break;p=p-next;Popopnd1(OPND,n);e=n;中缀表达式求值voidzhongzhui(Lnode*p)sqstack1OPND;运算数栈sqstack2OPTR;运算符栈intn;charc,c2;Lnode*first;first=p;p=p-next;InitStack1(OPND);InitStack2(OPTR);while(!stackempy2(OPTR)llp)while(p)switch(p-data)Push1(OPND,n);case1:n=p-data1;break;case2:c=p-data2;if(stackempy2(0PTR)Push2(0PTR,c);elseswitch(c)case(:Push2(OPTR,c);break;case):GetTop2(OPTR,c2);while(c2!=()Operat(OPND,OPTR);GetTop2(OPTR,c2);Popopnd2(OPTR,c2);break;default:GetTop2(OPTR,c2);if(compare(c2,c)Push2(OPTR,c);elseOperat(OPND,OPTR);Push2(OPTR,c);break;break;default:printf();break;p=p-next;while(!stackempy2(OPTR)Operat(OPND,OPTR);Popopndl(OPND,n);p=first-next;while(p)if(p-data=l)printf(%d,p-datal);if(p-data=2)printf(%c,p-data2);p=p-next;printf(=%d,n);中缀表达式转化为后voidhouzhui(Lnode*p)缀表达式sqstack2OPTR;运算符栈Lnode*r,*q,*head;intn;charc,c2;InitStack2(OPTR);p=p-next;q=(Lnode*)malloc(sizeof(structNode);head=q;while(p)switch(p-data)case1:n=p-data1;r=(Lnode*)malloc(sizeof(structNode);q-next=r;q=q-next;q-data=1;break;q-data1=n;case2:c=p-data2;if(stackempy2(0PTR)Push2(0PTR,c);elseswitch(c)case(:Push2(OPTR,c);break;case):Popopnd2(OPTR,c2);while(c2!=()r=(Lnode*)malloc(sizeof(structNode);q-next=r;q=q_next;q-data=2;q-data2=c2;Popopnd2(OPTR,c2);break;default:GetTop2(OPTR,c2);while(!compare(c2,c)Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(structNode);q-next=r;q=q-next;q-data=2;q-data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;default:printf();break;p=p_next;while(!stackempy2(0PTR)Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(structNode);q-next=r;q=q_next;q-data=2;q-data2=c2;q-next=NULL;q=head-next;while(q)if(q-data=l)printf(%d,q-datal);if(q-data=2)printf(%c,q-data2);q=q-next;houzhuiqiuzhi(head,n);printf(=%d,n);voidqianzhuiqiuzhi(Lnode2*p,int&e)前缀表达式求值sqstack1OPND;运算数栈sqstack2OPTR;运算符栈intn;charc;Lnode2*head;head=p;p=p_next;InitStackl(OPND);InitStack2(OPTR);while(p!=head)switch(p-data)case1:n=p-data1;Push1(OPND,n);break;case2:c=p-data2;Push2(OPTR,c);Operatqianzhui(OPND,OPTR);break;default:printf();break;p=p-next;Popopnd1(OPND,n);e=n;voidqianzhui(Lnode*p)式sqstack2OPTR;运算符栈InitStack2(OPTR);intn;charc,c2;Lnode*first;Lnode2*q,*head,*r,*head2,*s;first=p;p=p_next;q=(Lnode2*)malloc(sizeof(structNode2);环链表head=q;while(p)r=(Lnode2*)malloc(sizeof(structNode2);q-next=r;r-prior=q;q=q-next;q-data=p-data;q-datal=p-datal;q-data2=p-data2;p=p-next;q-next=head;head-prior=q;中缀表达式转化为前缀表达建立存中缀表达式的双向循s=(Lnode2*)malloc(sizeof(structNode2);建立存前缀表达式的双向循环链表head2=s;while(q!=head)switch(q-data)casel:n=q-datal;r=(Lnode2*)malloc(sizeof(structNode2);s-next=r;r-prior=s;s=s-next;s-data=1;s-data1=n;break;case2:c=q-data2;if(stackempy2(0PTR)Push2(0PTR,c);elseGetTop2(OPTR,c2);if(c2=)Push2(OPTR,c);elseswitch(c)case):Push2(OPTR,c);break;case(:Popopnd2(OPTR,c2);default:while(c2!=)r=(Lnode2*)malloc(sizeof(structNode2);s-next=r;r-prior=s;s=s-next;s-data=2;s-data2=c2;Popopnd2(OPTR,c2);break;GetTop2(OPTR,c2);while(!compare(c2,c)Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(structNode2);s-next=r;r-prior=s;s=s-next;s-data=2;s-data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;default:printf();break;q=q_prior;while(!stackempy2(0PTR)Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(structNode2);s-next=r;r-prior=s;s=s-next;s-data=2;s-data2=c2;s-next=head2;head2-prior=s;while(s!=head2)if(s-data=l)printf(%d,s-data1);if(s-data=2)printf(%c,s-data2);s=s-prior;qianzhuiqiuzhi(head2,n);printf(=%d,n);intmain()charn10;charc;inti,j,k,a,b,z,y,e;Lnode*p,*q,*first;i=0;e=1;a=0;b=1;z=0;y=0;p=(Lnode*)malloc(sizeof(structNode);first=p;printf();doc=getchar();if(Ov=c&cv=9)ni=c;i+；elseswitch(c)case+:case-:case*:case/:case%:case(:case):casen:if(n00&n0v=9)q=(Lnode*)malloc(sizeof(structNode);p_next=q;p=p_next;for(k=0;kvi;k+)for(j=0;jv=i-k-2;j+)e=e*10;a=a+(nk-0)*e;e=1;nk=0;p-data=1;p-datal=a;i=0;a=0;if(c!=n)if(p-data=2)if(p-data2!=)&c!=()b=0;q=(Lnode*)malloc(sizeof(structNode);p_next=q;p=p-next;p-data=2;p-data2=c;if(c=()z+;if(c=)y+;default:if(c!=+&c!=-&c!=*&c!=7&c!=%&c!=n&c!=(&c!=)b=0;while(c!=n);if(z!=y)b=0;p-next=NULL;if(b=0)printf(输入中缀表达式有误)；elseprintf(输入1中缀表达式求值，输入2后缀表达式求值，输入3前缀表达式求值)；scanf(%d,&b);if(b=1)zhongzhui(first);if(b=2)houzhui(first);if(b=3)qianzhui(first);return1;
展开阅读全文