C语言实现中缀、后缀、前缀表达式

1、1表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式如：2274-*3/11+和前缀式如：+11/*22-743。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计1表达式求值问题定义存储中缀表达式的结点类型由丁表达式中有字符与数字两种类型，故定义结点一个标志域data,标志结点存储的为字符data=2还是数字data=1,再寻找结点中对应的

2、存储位置，读取数字域data1字符域data2。而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。typedefstructNode(intdata;intdata1;chardata2;structNode*next;Lnode;typedefstructNode2/定义存储前缀表达式的结点类型(intdata;intdata1;chardata2;structNode2*next;structNode2*prior;Lnode2;3.运行、测试与分析1表达式求值问题1按提示输入中缀表达式，如图。如输入中缀表达式不正确，提示输入有误，如图1

3、.2,1.3所示。图a图(2)选择表达式转换并求值方式。按“1”选择中缀表达式求值，如图1.4所示。3按“2”选择中缀表达式转变为后缀表达式并求值，如图1.5所示图1.5(4)按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示'C:'Users.Adninistr占t&rDes<topDebugJntitledLexe'疳锯袅迁策值，输入2后蝴表达式求值/-*34FR3411=1R2Pprs?nukeuto输入3前缀表达式求值3nnritimiiR图1.6附录：源代码1表达式求值问题#include<stdio.h>#include&

4、lt;stdlib.h>#defineMAXNUM100typedefstructNode/定义存储中缀表达式的结点类型intdata;intdata1;chardata2;structNode*next;Lnode;typedefstructNode2定义存储前缀表达式的结点类型intdata;intdata1;chardata2;structNode2*next;structNode2*prior;Lnode2;typedefintselemtype1;定义运算数栈的结点typedefstruct定义运算数栈的类型selemtype1*base;selemtype1*top;sqst

5、ack1;voidInitStack1(sqstack1&s)新建一个空运算数栈s.base=(selemtype1*)malloc(MAXNUM*sizeof(selemtype1);s.top=s.base;if(!s.base)printf("出错：申请空间失败！n");voidPush1(sqstack1&s,selemtype1&e)运算数栈，入栈：插入元素e为新的栈顶元素if(s.top-s.base>=MAXNUM)printf("出错：表达式过长！1n");*s.top+=e;voidGetTop1(sqst

6、ack1s,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;v

7、oidInitStack2(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,sel

8、emtype2&e)运算符栈，用e返回栈顶元素(e=*(s.top-1);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='*'|c='/'|c='%')i=2;elseif(c='+

9、'|c='-')i=1;elsei=0;intcompare(chara,charb)/比较栈顶元素运算符与外部运算符优先级大小，外部优先级大则返回1,反之返回0(intin,out;priority(a,in);priority(b,out);if(out>in)return1;elsereturn0;voidOperat(sqstack1&OPND,sqstack2&OPTR)(intnum1,num2,num;charc;Popopnd1(OPND,num2);Popopnd1(OPND,num1);Popopnd2(OPTR,c);swit

10、ch(c)(case'+':num=num1+num2;break;case'-':num=num1-num2;break;case'*':num=num1*num2;break;case'/':num=num1/num2;break;case'%':num=num1%num2;break;Push1(OPND,num);voidOperatqianzhui(sqstack1&OPND,sqstack2&OPTR)(intnum1,num2,num;charc;Popopnd1(OPND,num1)

11、;Popopnd1(OPND,num2);Popopnd2(OPTR,c);switch(c)(case'+':num=num1+num2;break;case'-':num=num1-num2;break;case'*':num=num1*num2;break;case'/':num=num1/num2;break;case'%':num=num1%num2;break;Push1(OPND,num);后缀表达式求值voidhouzhuiqiuzhi(Lnode*p,int&e)(sqstack1OPND

12、;运算数栈sqstack2OPTR;运算符栈intn;charc;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p)(switch(p->data)(case1:n=p->data1;Push1(OPND,n);break;case2:c=p->data2;Push2(OPTR,c);Operat(OPND,OPTR);break;default:printf("结点有误");break;p=p->next;Popopnd1(OPND,n);e=n;中缀表达式求值voidzhongzhui(

13、Lnode*p)sqstack1OPND;运算数栈sqstack2OPTR;运算符栈intn;charc,c2;Lnode*first;first=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(!stackempy2(OPTR)|p)while(p)switch(p->data)case1:n=p->data1;Push1(OPND,n);break;case2:c=p->data2;if(stackempy2(OPTR)Push2(OPTR,c);elseswitch(c)case'(':Pus

14、h2(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(!stackem

15、py2(OPTR)Operat(OPND,OPTR);Popopnd1(OPND,n);p=first->next;while(p)(if(p->data=1)printf("%d",p->data1);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;InitStac

16、k2(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;q->data1=n;break;if(stackempy2(OPTR)Push2(OPTR,c);elseswitch(c)case'(':Push2(OPTR,c);break;case')&#

17、39;: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-&g

18、t;data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;default:printf("结点有误");break;p=p->next;while(!stackempy2(OPTR)(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=1)printf

19、("%d",q->data1);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!

20、=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

21、,*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->data1=p->data1;q->data2=p->data2;p=p->next;q->next=head;head->prior=q;s=(Lnode2*)mall

22、oc(sizeof(structNode2);链表head2=s;中缀表达式转化为前缀表达/建立存中缀表达式的双向循/建立存前缀表达式的双向循环while(q!=head)(switch(q->data)(case1:n=q->data1;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(OPTR)Push2(OPTR,c);else(GetTo

23、p2(OPTR,c2);if(c2=')')Push2(OPTR,c);else(switch(c)(case')':Push2(OPTR,c);break;case'(':Popopnd2(OPTR,c2);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;default:GetTop2(OP

24、TR,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(OPTR)Popopnd2(OPTR,c2);r=(Lnode2*)

25、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=1)printf("%d”,s->data1);if(s->data=2)printf("%c”,s->data2);s=s->prior;qianzhuiqiuzhi(head2,n);printf("=%d",n

26、);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("请输入中缀表达式");do(c=getchar();if('0'<=c&&c<='9')(ni=c;i+；else(switch(c)(case'+':case'-':case'*':case'/':case'%':case'(':case')':case'n':(if(n0>'0'&&