(完整word版)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 de2;3.运行、测试与分析(

3、1)表达式求值问题(1)按提示输入中缀表达式，如图 1.1 所示。如输入中缀表达式不正确, 提示输入有误，如图 121.3 所示。/定义存储前缀表达式的结点类型图 1.1IAUsersAdm i r；5trat?rDeFktopDebugU ntit led 1 exe请險入中壊表达式i 24吋输入口缀表达式有误ess any key to contimue图 1.2图 1.3(2)选择表达式转换并求值方式。按“ 1”选择中缀表达式求值，如图 1.4 所示。 C :User5Adm ini 5tratorDe sktopDebugU ntit led 1*罷紅吊蛭达式策值，输入2后缀表达式求值

4、，输入瑜缀表达式求值亠12 + /11 =182 Press etny key to continue图 1.4(3)按“ 2”选择中缀表达式转变为后缀表达式并求值，如图1.5 所示图 1.5(4)按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6 所示图 1.6附录：源代码IAUsersAdm i r；5trat?rDeFktopDebugU ntit led 1 exe(1)表达式求值问题#i nclude#i nclude#defi ne MAXNUM 100typedef struct Node intdata;int data1;char data2;struct Node *

5、n ext;Lno de;typedef struct Node2int data;int data1;char data2;struct Node2 *n ext;struct Node2 *prior;Lno de2;typedef struct/定义运算数栈的类型selemtype1 *base;selemtype1 *top;sqstack1;void Ini tStack1(sqstack1 &s)/ 新建一个空运算数栈s.base=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1);s.top=s.base;/定义存储中缀表达式的结

6、点类型/定义存储前缀表达式的结点类型typedef int selemtype1;/定义运算数栈的结点if(!s.base) pri ntf(出错：申请空间失败！n);void Push1(sqstack1 &s,selemtype1 &e)/运算数栈，入栈：插入元素 e 为新的栈顶元素 if(s.top-s.base=MAXNUM)printf(出错：表达式过长！ 1n);*s.top+ =e;void GetTop1(sqstack1 s,selemtype1 &e)运算数栈，用 e 返回栈顶元素e=*(s.top-1);void Popopnd1(sqstack1

7、 &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/定义运算符栈类型selemtype2 *base;selemtype2 *top;sqstack2;void In itStack2(sqstack2 &s)/ 新建一个空运算符栈s.b

8、ase=(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)printf(出错：表达式过长！2n);*s.top+ =e;void GetTop2(sqstack2 s,selemtype2 &e)运算符栈，用 e 返回栈顶元素e=*(s.top-1);void Popo

9、pnd2(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 nt &i)/ 确定运算符优先级if (c=*|c=/|c=%) i=2 ;else if (c=屮|c=-) i=1 ;else i=0;in t compare(char a,char b)/比较栈顶元素运算符与

10、外部运算符优先级大小，外部优先级大则返回 1,反之返回 0int in,o ut;priority(a,i n);priority(b,out);if(outi n) return 1;else return 0;void Operat(sqstack1 & OPND,sqstack2 & 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 -: nu

11、m=nu m1-nu m2;break;case *: num=nu m1* nu m2;break;case /: num=nu ml/ nu m2;break;case %: num=nu ml% nu m2;break;Push1(OPND ,n um);switch(p-data)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);swi

12、tch(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=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)

13、;In itStack2(OPTR);while(p)case 1:n=p-data1;/后缀表达式求值case 1:n=p-data1;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 *fir

14、st;first=p;p=p-n ext;In itStack1(OPND);In itStack2(OPTR);while(!stackempy2(OPTR)|p) while(p)switch(p-data)Push1(OPND, n);/中缀表达式求值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,OPTR);GetTop2(OPTR,c2);

15、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;q-data1= n;while(p)if(p-data=1) pri ntf(%d ,p-data1)

16、; 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(struct Node);head=q;while(p) switch(p-data)case 1:n=p-data1;r=(L no de*)malloc(sizeof(struct Node);q-n e

17、xt=r;q=q-n ext;q-data=1;break;/中缀表达式转化为后case 2:c=p-data2;if(stackempy2(0PTR) Push2(0PTR,c);else switch(c) case (: Push2(OPTR,c);break;case ): Popop 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,

18、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-data=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-

19、n ext;q-data=2;q-data2=c2;q- next=NULL;q=head-n ext;while(q)if(q-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=

20、p-n 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;/ 运算符栈In itStack2(OPTR);int

21、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-data2;p=p-n ext;q-n ext=head;head-prior=q;s=(L node2*)malloc

22、(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-data1= n;break;case 2:c=q-data2;if(stackempy2(0PTR) Push2(0PTR,c);else GetTop2(OPTR,c2);if(c2=) Push2(

23、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-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(stru

24、ct 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;default: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-data1); if(s-data=2) pri ntf(%c,s-data2)