将中缀表达式转换为后缀表达式并计算

1、数据结构实验报告实验题目:使用键盘输入表达式，计算表达式的值并输出；将表达式转化成后缀表达式输出，利用后缀表达式求表达式的值并输出。实验目的:使用栈的操作编写关于数据结构的程序。实验内容:写出程序并上机调试、通过。、需求分析1、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“请输入表达式”时输入中缀表达式。然后计算机终端输出转换后的后缀表达式及计算后 的结果。2、程序执行的命令包括:（1）构造链栈；（2）输入数据；（3）判断输入的表达式是否为非法表达式;（4）将中缀表达式转换为后缀表达式；（5）计算表达式的值；（6）输出。（7）结束4、本程序能将中缀表达式转换为后缀表达式，并且能计

2、算表达式的值。5、输入及输出示例:请输入表达式6+3* (6+5 ) 后缀表达式：6 3 6 5 + * +计算结果为：39P ress any key to con ti nue请输入表达式6-3* (7+1ERROR表达式错误P ress any key to con ti nue概要设计1.基本操作(1) 、struct node操作结果：创建结构体(2) 、int Searchexpression(char string1)初始条件：表达式string1已经存在。操作结果：判断表达式是否非法(3) 、 struct node *lnitialization()操作结果：创建栈链。(4)

3、 、struct node *assort(struct node *s)初始条件：string1、string2已存在。操作结果：将中缀表达式转换为后缀表达式并存在string2 中。(5) 、struct node *calcolate(struct node *s)操作结果：求出表达式的值2、模块调用图主程序模块创建结构体判断表达式是否非法将中缀表达式转换为后缀表达式表达式求值三详细设计1、每个模块:(1)定义结构体 struct nodechar data;int num;struct node *n ext;；(2) 判断表达式是否非法 int Searchex pressi on(

4、 char stri ng1)int i1,b1,b2;int m;m=strle n(stri ng1);if(stri ng10v0|stri ng109)printf(ERROR:表达式缺操作数！ n);retum(WRONG);for(i1=0;i1=m;i1+)if(stri ng1i1=()b1+;elseif(stri ng1i1=)b2+;if(b1!=b2)printf(ERROR:缺少括号 n);return(WRONG);for(i1=0;i1m;i1+)if(0v=stri ng1i1&stri ng1i1v=9&0=stri ng1i1+1&str in g1i1+1

5、=9) printf(ERROR:表达式缺操作符！ n);return(WRONG);for(i1=0;i1v=m;i1+)if(stri ng1i1=+&(stri ng1i1+1=+|stri ng1i1+1=-|stri ngiii+i=*|stri ng1i1+1=7) printf(ERROR:表达式缺操作数！ n);retum(WRONG); elseif(stri ng1i1=-&(stri ng1i1+1=+|stri ng1i1+1=-|strin g1i1+1=*|stri ng1i1+1=7) printf(ERROR:表达式缺操作数！ n);return(WRONG);

6、 elseif(stri ng1i1=*&(stri ng1i1+1=+|stri ng1i1+1=-|strin g1i1+1=*|stri ng1i1+1=7)prin tf(ERROR:表达式缺操作数！n);return(WRONG);elseif(stri ng1i1=/&(stri ng1i1+1=+|stri ng1i1+1=-|string1i1+1=*|stri ng1i1+1=7)prin tf(ERROR:表达式缺操作数！n);retum(WRONG);retum(RIGHT);输入字符串(3) 、将中缀表达式转换为后缀表达式 struct node *assort(str

7、uct node *s)/struct node *p ,*t op;int i;top=s;int m;char a;m=strle n(stri ng1);for(i=0;idata=a ;p-n ext=t op;top=p;break;case *: case /:strin g2j= ;j+;if(to p-data=-*)|(to p-data=-/)stri ng2|j=t op-data;j+; /比其高，现将栈顶运算符出栈，再进栈。top-data=a;break;else否,p=(struct node *)malloc(sizeof(struct no de);/直接进栈

8、p-data=a ;p-n ext=t op;top=p;break;case +: case -:strin g2j= ;j+;if(t op-data=+|t op-data=T|t op-data=*|t op-data二 =/)stri ng2|j=t op-data;j+;top-data=a;break;else p-data=a ;p-n ext=t op;top=p;break;case ):strin g2j= ;j+;if(to p-data=) prin tf(i nput error);break; while(to p-data!=()stri ng2|j=t op-

9、data;j+;p=t op;top=top-n ext;free( p);p=top ;t op=top-n ext;free( p);break;while(to p-data!=)stri ng2|j=t op-data;j+;p=t op;top=top-n ext;free( p);strin g2j=#;printf(后缀表达式为:);for(i=0;ij;i+)if(stri ng2i!=)prin tf(%c ,stri ng2i);prin tf(n );return top;(4)表达式求值 struct node *calcolate(struct node *s)str

10、uct node *top : p;char *q;int x,y,a;int i,n;top=s;/指向栈顶的指针for(i=0;i=0&stri ng2iv=9)q=&stri ng2i;a=atoi(q);for(n=i;stri ng2 n=0&stri ng2 nv=9; n+)p=(struct node *)malloc(sizeof(struct node );p-num=a;p-n ext=t op ;t op=p;i=n-1;elseif(stri ng2i=#)/遇#号结束标志，输出栈中的最后计算结果printf(计算结果为：dn,top-num);elseif(stri

11、 ng2i= )elsey=t op-num;p=top ;t op=top-n ext;free( p);x=t op-num;p=top ;t op=top-n ext;free( p);switch(stri ng2i) case +:a=x+y;p=(struct node *)malloc(sizeof(struct no de);p-num=a;p-n ext=t op ;t op=p;break; case -:a=x-y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-n ext=t op ;t op=p;break

12、;case *:a=x*y;p=(struct node *)malloc(sizeof(struct node );p-num=a;p-n ext=t op ;t op=p;break;case 7:if(y=0)printf(ERROR:除数为零!n);a=(float)x/y;p-num=a;p-n ext=t op ;t op=p;p=(struct node *)malloc(sizeof(struct node );break;return 0;(5)、主函数void mai n()struct node *top, *head;top=1 ni tializatio n();/建

13、立一个链栈，并返回栈顶指针printf(请输入表达式：n);gets(stri ng1);if(Searchex pressio n(stri ng1)head=assort(to p);/中缀转化为后缀表达式calcolate(head);2、完整函数#i ncludevstdio.h#i ncludevmalloc.h #i ncludevstri ng.h #in clude #defi ne MAX 60 #defi ne RIGHT 1 #defi ne WRONG 0 #defi ne DEMAX 15 #defi ne NULL 0 char stri ng1MAX;char s

14、tri ng2MAX;int j=O;struct n ode / 定义结构体。char data;int num;struct node *n ext;/判断非法表达式;int Searchex pressi on( char stri ng1)int i1,b1,b2;int m;m=strle n(stri ng1);if(stri ng10v0|stri ng109)printf(ERROR:表达式缺操作数！ n);retum(WRONG);for(i1=0;i1=m;i1+)if(stri ng1i1=()b1+;elseif(stri ng1i1=)b2+;if(b1!=b2)pr

15、intf(ERROR:缺少括号 n);return(WRONG);for(i1=0;i1m;i1+)if(0v=stri ng1i1&stri ng1i1v=9& 0=stri ng1i1+1&stri ng 1i1+1=9) printf(ERROR:表达式缺操作符！ n);return(WRONG); for(i1=0;i1data=;top-num=0;top-n ext=NULL;输入字符串return top;struct node *assort(struct node *s)/struct node *p ,*t op;int i;top=s;int m;char a;m=str

16、le n(stri ng1);for(i=0;idata=a ;p-n ext=t op;top=p;break;case *: case /:strin g2j= ;j+;if(to p-data=*)|(to p-data=-/)stri ng2j=t op-data;j+;/比其高，现将栈顶运算符出栈，再进栈。top-data=a;break;else否，直接p=(struct node *)malloc(sizeof(struct no de);/进栈p-data=a ;p-n ext=t op;top=p;break;case +: case -:strin g2j= ;j+;if(

17、t op-data=+|t op-data=-|t op-data=*|t op-data=7)stri ng2|j=t op-data;j+;top-data=a;break;elsep=(struct node *)malloc(sizeof(struct no de);p-data=a ;p-n ext=t op;top=p;break;case ):strin g2j= ;j+;if(to p-data=) prin tf(i nput error);break;while(to p-data!=()stri ng2|j=t op-data;j+;p=t op;top=top-n ex

18、t;free( p);p=top ;t op=top-n ext;free( p);break;while(to p-data!=)stri ng2|j=t op-data;j+;p=t op;top=top-n ext;free( p);stri ng2j=#;printf（后缀表达式为:）;for(i=0;ij;i+)if(stri ng2i!=)prin tf(%c ,stri ng2i);return top;prin tf(n );/计算表达式的值struct node *calcolate(struct node *s)struct node *top ,* p;char *q;i

19、nt x,y,a;int i,n;top=s;/指向栈顶的指针for(i=0;i=0&stri ng2iv=9)q=&stri ng2i;a=atoi(q);for(n=i;stri ng2 n=0&strin g2 nnum=a;p-n ext=t op ;t op=p;i=n-1;elseprintf(” 计算结果为：dn,top-num);if(stri ng2i=#)/遇#号结束标志，输出栈中的最后计算结果elseif(stri ng2i= ) elsey=t op-num;p=top ;t op=top-n ext;free( p);x=t op-num;p=top ;t op=top-n ext;free( p);switch(stri ng2i) case +:a=x+y;p=(struct node *)malloc(sizeof(struct no de);p-num=a;p-n ext=t op ;t op=p;break; case -:a=x-y;p=(struct node *)malloc(sizeof(struct node