C语言实现中缀、后缀、前缀表达式相互转化并求值

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

2、还是数字data=1，再寻找结点中对应的存储位置，读取 数字域data1字符域data2。而在前缀表达式时，存在表达式逆序，因表达式类型 不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。typedef struct Node/定义存储中缀表达式的结点类型int data;int data1;char data2;struct Node *n ext;/定义存储前缀表达式的结点类型Lno de;typedef struct Node2 int data;int data1;char data2;struct Node2 *n ext;struct Node2 *prior; Lno de

3、2;3. 运行、测试与分析(1)表达式求值问题(1)按提示输入中缀表达式，如图 1.1所示。如输入中缀表达式不正确, 提示输入有误，如图121.3所示。图1.1图1.2图1.3(2) 选择表达式转换并求值方式。按“1”选择中缀表达式求值，如图1.4所示。 'C :User5Adm ini 5tratorDe sktopDebugU ntit led 1*罷紅吊蛭达式策值，输入2后缀表达式求值，输入瑜缀表达式求值亠12 + <34 *56 -34 >/11 =182 Press etny key to continue图1.4(3) 按“ 2”选择中缀表达式转变为后缀表达式并

4、求值，如图1.5所示*C:U sers Admin ist ratorDe 5 ktopDebu gUntitiledl.exeIi*输入中綴表达或丄/< J吨*5 A J吗"：u输头曲醸达式隶值.输入2后缀喪达式求值，输入M前绿表达武求值212 34 56 *34 -11 /+=182 Press an key to continue.图1.5(4) 按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示图1.6附录：源代码(1)表达式求值问题#i nclude<stdio.h>#i nclude<stdlib.h>#defi ne MAXNUM

5、 100 typedef struct Node int data;int data1;char data2;struct Node *n ext;Lno de;typedef struct Node2int data;int data1;char data2;struct Node2 *n ext;struct Node2 *prior;/定义存储中缀表达式的结点类型/定义存储前缀表达式的结点类型typedef int selemtype1;/定义运算数栈的结点Lno de2;typedef struct/定义运算数栈的类型selemtype1 *base;selemtype1 *top;s

6、qstack1;void Ini tStack1(sqstack1 &s)/ 新建一个空运算数栈s.base=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1);s.top=s.base;if(!s.base) pri ntf("出错：申请空间失败！n");void Push1(sqstack1 &s,selemtype1 &e)/运算数栈，入栈：插入元素 e 为新的栈顶元素 if(s.top-s.base>=MAXNUM)printf("出错：表达式过长！1n");*s.top+

7、=e;void GetTop1(sqstack1 s,selemtype1 &e)运算数栈，用 e返回栈顶元素e=*(s.top-1);void Popopnd1(sqstack1 &s,selemtype1 &e) /运算数栈，退栈：删除栈顶元素， 并用e返回其值e=*-s.top;int stackempy1(sqstack1 s) /运算数栈，若为空栈返回1，否则返回0if(s.top=s.base) retur n 1;else return 0;typedef char selemtype2;/定义运算符栈的结点类型typedef struct/定义运算符栈类

8、型selemtype2 *base;selemtype2 *top;sqstack2;void In itStack2(sqstack2 &s)/ 新建一个空运算符栈s.base=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2);s.top=s.base;if(!s.base) pri ntf("出错：申请空间失败！n");void Push2(sqstack2 &s,selemtype2 &e)/运算符栈，入栈：插入元素 e 为新的栈顶元素 if(s.top-s.base>=MAXNUM)print

9、f("出错：表达式过长！2n");*s.top+ =e;void GetTop2(sqstack2 s,selemtype2 &e)运算符栈，用 e返回栈顶元素e=*(s.top-1);void Popopnd2(sqstack2 &s,selemtype2 &e) /运算符栈，退栈：删除栈顶元素， 并用e返回其值e=*-s.top;int stackempy2(sqstack2 s) /运算符栈，若为空栈返回 1，否则返回0if(s.top=s.base) retur n 1;else return 0;void priority(char c,i

10、 nt &i)/ 确定运算符优先级if (c='*'|c='/'|c='%') i=2 ;else if (c=屮|c='-') i=1 ;else i=0;in t compare(char a,char b)/比较栈顶元素运算符与外部运算符优先级大小，外部优先级大则返回1,反之返回0int in,o ut;priority(a,i n);priority(b,out);if(out>i n) return 1;else return 0;void Operat(sqstack1 & OPND,sqstac

11、k2 & OPTR)int nu m1, num2,num;char c;Popop nd1(OPND ,n um2);Popop nd1(OPND ,n um1);Popop nd2(OPTR,c);switch(c)case '+': num=nu m1+ nu m2;break;case '-': num=nu m1-nu m2;break;case '*': num=nu m1* nu m2;break;case '/': num=nu ml/ nu m2;break;case '%': num=n

12、u ml% nu m2;break;Push1(OPND ,n um);void Operatqia nzhui(sqstack1 & OPND,sqstack2 & OPTR)int nu m1, num2,num;char c;Popop nd1(OPND ,n um1);Popop nd1(OPND ,n um2);Popop nd2(OPTR,c);switch(c)case '+': num=nu m1+ nu m2;break;case '-': num=nu m1-nu m2;break;case '*': num=

13、nu m1* nu m2;break;case '/': num=nu ml/ nu m2;break;case %: num=nu ml% nu m2;break;Push1(OPND ,n um);/后缀表达式求值void houzhuiqiuzhi(L node *p,i nt &e) sqstackl OPND;运算数栈sqstack2 OPTR; / 运算符栈 int n;char c;p=p->n ext;In itStackl(OPND);In itStack2(OPTR);while(p)case 1:n=p->data1;switch(p-

14、>data)Push1(0PND, n); break;case 2:c=p->data2;Push2(0PTR,c);Operat(OPND,OPTR); break;default:printf("结点有误"); break;p=p->n ext;Popop nd1(OPND, n);e=n;/中缀表达式求值void zho ngzhui(L node *p)sqstack1 OPND;运算数栈sqstack2 OPTR; / 运算符栈 int n;char c,c2;Lnode *first;first=p;p=p->n ext;In itSt

15、ack1(OPND);In itStack2(OPTR);while(!stackempy2(OPTR)|p) while(p)switch(p->data)Push1(OPND, n);case 1:n=p->data1;break;case 2:c=p->data2;if(stackempy2(0PTR) Push2(0PTR,c);else switch(c)case '(': Push2(OPTR,c);break;case ')': GetTop2(OPTR,c2);while(c2!='(')Operat(OPND,

16、OPTR);GetTop2(OPTR,c2);Popop nd2(OPTR,c2); break;default: GetTop2(OPTR,c2);if(compare(c2,c) Push2(OPTR,c); else Operat(OPND,OPTR);Push2(OPTR,c);break;break;default: printf("结点有误"); break;p=p->n ext;while(!stackempy2(OPTR) Operat(OPND,OPTR);Popop nd1(OPND, n);p=first- >n ext;while(p)i

17、f(p->data=1) pri ntf("%d ",p->data1); if(p->data=2) prin tf("%c",p->data2); p=p->n ext;prin tf("=%d ",n);/中缀表达式转化为后void houzhui(L node *p)缀表达式sqstack2 OPTR;/ 运算符栈Lnode *r,*q,*head;int n;char c,c2;In itStack2(OPTR);p=p->n ext;q=(L no de*)malloc(sizeof(s

18、truct Node);head=q;while(p) switch(p->data)case 1:n=p->data1;r=(L no de*)malloc(sizeof(struct Node);q->n ext=r;q=q->n ext;q->data=1;break;q->data1= n;case 2:c=p->data2;if(stackempy2(0PTR) Push2(0PTR,c);else switch(c) case '(': Push2(OPTR,c);break;case ')': Popop

19、nd2(OPTR,c2);while(c2!='(') r=(L no de*)malloc(sizeof(struct Node); q->n ext=r;q=q->n ext;q->data=2;q->data2=c2;Popop nd2(OPTR,c2);break;default: GetTop2(OPTR,c2);while(!compare(c2,c) Popop nd2(OPTR,c2);r=(L no de*)malloc(sizeof(struct Node); q->n ext=r;q=q->n ext;q->dat

20、a=2;q->data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;default: printf("结点有误");break;p=p->n ext;while(!stackempy2(0PTR) Popop nd2(OPTR,c2);r=(L no de*)malloc(sizeof(struct Node);q->n ext=r;q=q->n ext;q->data=2;q->data2=c2;q-> next=NULL;q=head->n ext;while(q)if(q

21、->data=1) pri ntf("%d ",q->data1);if(q->data=2) prin tf("%c",q->data2);q=q->n ext;houzhuiqiuzhi(head ,n);prin tf("=%d ",n);void qia nzhuiqiuzhi(L node2 *p,int &e)前缀表达式求值sqstack1 OPND;运算数栈sqstack2 OPTR;/ 运算符栈int n;char c;Lno de2 *head;head=p;p=p->n

22、ext;In itStackl(OPND);In itStack2(OPTR);while(p!=head)switch(p->data)case 1:n=p->data1;Push1(OPND, n);break;case 2:c=p->data2;Push2(OPTR,c);Operatqia nzhui(OPND,OPTR);break;default:printf("结点有误");break;p=p->n ext;Popop nd1(OPND, n);e=n;void qianzhui(Lnode *p)式sqstack2 OPTR;/ 运算

23、符栈In itStack2(OPTR);int n;char c,c2;Lnode *first;Ln ode2 *q,*head,*r,*head2,*s;first=p;p=p->n ext;q=(Lnode2*)malloc(sizeof(struct Node2);环链表head=q;while(p)r=(L node2*)malloc(sizeof(struct Node2);q->n ext=r;r->prior=q;q=q->n ext;q->data=p->data;q->data1=p->data1;q->data2=p-

24、>data2;p=p->n ext;q->n ext=head;head->prior=q;s=(L node2*)malloc(sizeof(struct Node2);链表head2=s;/中缀表达式转化为前缀表达/建立存中缀表达式的双向循/建立存前缀表达式的双向循环while(q!=head)switch(q->data)case 1:n=q->data1;r=(L node2*)malloc(sizeof(struct Node2);s->n ext=r;r->prior=s;s=s->n ext;s->data=1;s-&g

25、t;data1= n;break;case 2:c=q->data2;if(stackempy2(0PTR) Push2(0PTR,c);else GetTop2(OPTR,c2);if(c2=')') Push2(OPTR,c);else switch(c) case ')':Push2(OPTR,c);break;case '(': Popop nd2(OPTR,c2);while(c2!=')') r=(L node2*)malloc(sizeof(struct Node2); s->n ext=r;r->

26、prior=s;s=s->n ext;s->data=2;s->data2=c2;Popop nd2(OPTR,c2);break;default: GetTop2(OPTR,c2);while(!compare(c2,c) Popop nd2(OPTR,c2);r=(L node2*)malloc(sizeof(struct Node2); s->n ext=r;r->prior=s;s=s->n ext;s->data=2;s->data2=c2;GetTop2(OPTR,c2);Push2(OPTR,c);break;break;defau

27、lt:printf("结点有误");break;q=q->prior; while(!stackempy2(OPTR) Popop nd2(OPTR,c2);r=(L node2*)malloc(sizeof(struct Node2);s->n ext=r;r->prior=s;s=s->n ext;s->data=2;s->data2=c2;s->n ext=head2;head2->prior=s;while(s!=head2)if(s->data=1) pri ntf("%d ",s->

28、data1); if(s->data=2) pri ntf("%c",s->data2); s=s->prior;qia nzhuiqiuzhi(head2 ,n);prin tf("=%d ",n);int main() char n10;char c;int i,j,k,a,b,z,y,e;Lnode *p,*q,*first;i=0;e=1;a=0;b=1;z=0;y=0;p=(L no de*)malloc(sizeof(struct Node); first=p;printf("请输入中缀表达式");do c = getchar();if('O'v=c&&c<='9') ni=c;i+；else switch (c) case '+':case '-':case '*':case '/':case %:case '(':case ')&#