《2022年C语言实现中缀、后缀、前缀表达式相互转化并求值 2.pdf》由会员分享，可在线阅读，更多相关《2022年C语言实现中缀、后缀、前缀表达式相互转化并求值 2.pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1. 问题描述（1）表达式求值问题表达 式 是 数 据 运算 的 基 本形 式 。 人 们 的 书 写习 惯 是 中缀 式 ， 如 ：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如： + 11 / * 22 7 4 3） 。后缀表达式和前缀表达式中没有括号，给计算带来方便。 如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2. 数据结构设计（1）表达式求值问题由于表达式中有字符与数字两种类型，故定义结点一个标志域
2、data，标志结点存储的为字符data=2 还是数字 data=1，再寻找结点中对应的存储位置，读取数字域 data1, 字符域 data2。而在前缀表达式时， 存在表达式逆序， 因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。typedef struct Node /定义存储中缀表达式的结点类型int data; int data1; char data2; struct Node *next; Lnode; typedef struct Node2 /定义存储前缀表达式的结点类型int data; int data1; char data2; struct Node2
3、*next; struct Node2 *prior; Lnode2; 3. 运行、测试与分析（1）表达式求值问题（1）按提示输入中缀表达式，如图1.1 所示。如输入中缀表达式不正确，提示输入有误，如图1.2,1.3所示。图 1.1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - 图 1.2 图 1.3（2）选择表达式转换并求值方式。按“1”选择中缀表达式求值，如图1.4所示。图 1.4（3）按“ 2”选择中缀表达式转变为后缀
4、表达式并求值，如图1.5 所示。图 1.5 （4）按“ 3”选择中缀表达式转变为前缀表达式并求值，如图1.6 所示。图 1.6 附录：源代码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - （1）表达式求值问题#include #include #define MAXNUM 100 typedef struct Node /定义存储中缀表达式的结点类型int data; int data1; char data2; struct
5、 Node *next; Lnode; typedef struct Node2 /定义存储前缀表达式的结点类型int data; int data1; char data2; struct Node2 *next; struct Node2 *prior; Lnode2; typedef int selemtype1; /定义运算数栈的结点typedef struct /定义运算数栈的类型selemtype1 *base; selemtype1 *top; sqstack1; void InitStack1(sqstack1 &s) /新建一个空运算数栈s.base=(selemtype1
6、*)malloc(MAXNUM*sizeof(selemtype1); s.top=s.base; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - if(!s.base) printf(出错：申请空间失败！ n); void Push1(sqstack1 &s,selemtype1 &e) /运算数栈，入栈：插入元素e 为新的栈顶元素 if(s.top-s.base=MAXNUM) printf( 出错：表达式过长！ 1n);
7、 *s.top+ =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，否则返回 0 if(s.top=s.base) return 1; else return 0; typedef char selemtype2; /定义运算符栈的结点类型typedef struct /
8、定义运算符栈类型selemtype2 *base; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - selemtype2 *top; sqstack2; void InitStack2(sqstack2 &s) /新建一个空运算符栈s.base=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2); s.top=s.base; if(!s.base) printf(出错：申请空间失败！
9、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 Popopnd2(sqstack2 &s,selemtype2 &e) /运算符栈，退栈：删除栈顶元素，并用 e返回其值e=*-s.top; int stackempy2(sqstack2 s) /运算符栈
10、，若为空栈返回1，否则返回 0 if(s.top=s.base) return 1; else return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - void priority(char c,int &i) /确定运算符优先级if (c=*|c=/|c=%) i=2 ; else if (c=+|c=-) i=1 ; else i=0; int compare(char a,char b) /比较栈顶元素运算符与
11、外部运算符优先级大小，外部优先级大则返回1，反之返回 0 int in,out; priority(a,in); priority(b,out); if(outin) return 1; else return 0; void Operat(sqstack1 &OPND,sqstack2 &OPTR) int num1,num2,num; char c; Popopnd1(OPND,num2); Popopnd1(OPND,num1); Popopnd2(OPTR,c); switch(c) case +:num=num1+num2;break; case -:num=num1-num2;br
12、eak; case *:num=num1*num2;break; case /:num=num1/num2;break; case %:num=num1%num2;break; Push1(OPND,num); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - void Operatqianzhui(sqstack1 &OPND,sqstack2 &OPTR) int num1,num2,num; char c; Popopnd
13、1(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; case /:num=num1/num2;break; case %:num=num1%num2;break; Push1(OPND,num); void houzhuiqiuzhi(Lnode *p,int &e) /后缀表达式求值sqstack1 OPND; /运算数栈sqstack2 OPTR; /
14、运算符栈int n; char c; p=p-next; InitStack1(OPND); InitStack2(OPTR); while(p) switch(p-data) case 1:n=p-data1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 - - - - - - - - - Push1(OPND,n); break; case 2:c=p-data2; Push2(OPTR,c); Operat(OPND,OPTR); break; def
15、ault:printf( 结点有误 ); break; p=p-next; Popopnd1(OPND,n); e=n; void zhongzhui(Lnode *p) /中缀表达式求值sqstack1 OPND; /运算数栈sqstack2 OPTR; /运算符栈int n; char c,c2; Lnode *first; first=p; p=p-next; InitStack1(OPND); InitStack2(OPTR); while(!stackempy2(OPTR)|p) while(p) switch(p-data) case 1:n=p-data1; Push1(OPND
16、,n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - break; case 2:c=p-data2; if(stackempy2(OPTR) Push2(OPTR,c); else switch(c) case (: Push2(OPTR,c);break; case ): GetTop2(OPTR,c2); while(c2!=() Operat(OPND,OPTR); GetTop2(OPTR,c2); Popopn
17、d2(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-next; while(!stackempy2(OPTR) Operat(OPND,OPTR); Popopnd1(OPND,n); p=first-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
18、 - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - while(p) if(p-data=1) printf(%d ,p-data1); if(p-data=2) printf(%c,p-data2); p=p-next; printf(=%d ,n); void houzhui(Lnode *p) /中缀表达式转化为后缀表达式sqstack2 OPTR; /运算符栈Lnode *r,*q,*head; int n; char c,c2; InitStack2(OPTR); p=p-next; q=(Lnode*)malloc(si
19、zeof(struct Node); head=q; while(p) switch(p-data) case 1:n=p-data1; r=(Lnode*)malloc(sizeof(struct Node); q-next=r; q=q-next; q-data=1; q-data1=n; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - case 2:c=p-data2; if(stackempy2(OPT
20、R) Push2(OPTR,c); else switch(c) case (: Push2(OPTR,c);break; case ): Popopnd2(OPTR,c2); while(c2!=() r=(Lnode*)malloc(sizeof(struct Node); 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(s
21、truct Node); q-next=r; q=q-next; q-data=2; q-data2=c2; GetTop2(OPTR,c2); Push2(OPTR,c); break; break; default: printf(结点有误 ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - break; p=p-next; while(!stackempy2(OPTR) Popopnd2(OPTR,c2); r=(L
22、node*)malloc(sizeof(struct Node); 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(%d ,q-data1); if(q-data=2) printf(%c,q-data2); q=q-next; houzhuiqiuzhi(head,n); printf(=%d ,n); void qianzhuiqiuzhi(Lnode2 *p,int &e) /前缀表达式求值sqstack1 OPND; /运算数栈sqstack
23、2 OPTR; /运算符栈int n; char c; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - Lnode2 *head; head=p; p=p-next; InitStack1(OPND); InitStack2(OPTR); while(p!=head) switch(p-data) case 1:n=p-data1; Push1(OPND,n); break; case 2:c=p-data2; Push2(
24、OPTR,c); Operatqianzhui(OPND,OPTR); break; default:printf( 结点有误 ); break; p=p-next; Popopnd1(OPND,n); e=n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - void qianzhui(Lnode *p) /中缀表达式转化为前缀表达式sqstack2 OPTR; /运算符栈InitStack2(OPTR); int n;
25、char c,c2; Lnode *first; Lnode2 *q,*head,*r,*head2,*s; first=p; p=p-next; q=(Lnode2*)malloc(sizeof(struct Node2); /建立存中缀表达式的双向循环链表head=q; while(p) r=(Lnode2*)malloc(sizeof(struct Node2); 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
26、=q; s=(Lnode2*)malloc(sizeof(struct Node2); /建立存前缀表达式的双向循环链表head2=s; while(q!=head) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - switch(q-data) case 1:n=q-data1; r=(Lnode2*)malloc(sizeof(struct Node2); s-next=r; r-prior=s; s=s-next; s-
27、data=1; s-data1=n; break; case 2:c=q-data2; if(stackempy2(OPTR) Push2(OPTR,c); else GetTop2(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(struct Node2); s-next=r; r-prior=s; s=s-next; s-data=2; s-data2=c2;
28、Popopnd2(OPTR,c2); break; default: GetTop2(OPTR,c2); while(!compare(c2,c) Popopnd2(OPTR,c2); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - r=(Lnode2*)malloc(sizeof(struct Node2); s-next=r; r-prior=s; s=s-next; s-data=2; s-data2=c2; GetT
29、op2(OPTR,c2); Push2(OPTR,c); break; break; default:printf(结点有误 ); break; q=q-prior; while(!stackempy2(OPTR) Popopnd2(OPTR,c2); r=(Lnode2*)malloc(sizeof(struct Node2); s-next=r; r-prior=s; s=s-next; s-data=2; s-data2=c2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
30、16 页，共 20 页 - - - - - - - - - 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); 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=(Lnode*)m
31、alloc(sizeof(struct Node); first=p; printf( 请输入中缀表达式 ); do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - c = getchar(); if(0=c&c0&n0next=q; p=p-next; for(k=0;ki;k+) for(j=0;jdata=1; p-data1=a; i=0;a=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - -
32、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - if(c!=n) if(p-data=2) if(p-data2!=)&c!=() b=0; q=(Lnode*)malloc(sizeof(struct Node); p-next=q; p=p-next; p-data=2; p-data2=c; if(c=() z+; if(c=) y+; default: if(c!=+&c!=-&c!=*&c!=/&c!=%&c!=n&c!=(&c!=) b=0; while (c != n); if
33、(z!=y) b=0; p-next=NULL; if(b=0) printf( 输入中缀表达式有误 ); else printf( 输入 1 中缀表达式求值， 输入 2 后缀表达式求值， 输入 3 前缀表达式求值); scanf(%d,&b); if(b=1) zhongzhui(first); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - if(b=2) houzhui(first); if(b=3) qianzhui(first); return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -