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

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

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

3、truct 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 Searchexpressi on( char

4、 stri ng1)int i1,b1,b2;int m;m=strle n( stri ng1);if(stri ng10v0|stri ng109)printf(ERROR:表达式缺操作数！n);return(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(0=stri ng1i1&stri ng1i1v=9&0=stri ng1i1+1&strin g

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

6、(WRONG);elseif(stri ng1i1=*&(stri ng1i1+1=+|stri ng1i1+1=-|stri ng1i1+1=*|stri ng1i1+1=/)pri ntf(ERROR:表达式缺操作数！n);return(WRONG);elseif(stri ng1i1=/&(stri ng1i1+1=+|stri ng1i1+1=-|string1i1+1=*|stri ng1i1+1=/)pri ntf(ERROR:表达式缺操作数！n);return(WRONG);return(RIGHT);(3)、将中缀表达式转换为后缀表达式struct node *

7、assort(struct node *s)输入字符串struct node *p,*top;int i;top=s;int m;char a;m=strle n( stri ng1);for(i=0;i=m;i+)a=stri ng1i;if(0data=a;p-n ext=top;top=p;break;case *:case /:stri ng2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，现将栈顶运算符出栈，再进栈。top-data=a;break; elsep=(struct node *)malloc(si

8、zeof(struct no de);p=(struct node *)malloc(sizeof(struct no de);/直接进栈p-data=a;p-n ext=top;top=p;break;case +:case -:stri ng2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=/)stri ng2j=top-data;j+;top-data=a;break;else否,p-data=a;p-n ext=top;top=p; break;case ):stri ng2j= ;j+;if(top-data=)pri ntf(

9、i nput error);break;while(top-data!=() stri ng2j=top-data;j+;p=top;top=top-n ext;free(p);p=top;top=top-n ext;free(p);break;struct node *top,*p;while(top-data!=)stri ng2j=top-data;j+;p=top;top=top-n ext;free(p);stri ng2j=#;printf(后缀表达式为:);for(i=0;ij;i+)if(stri ng2i!=)prin tf(%c ,stri ng2i);prin tf(n

10、);return top;(4)表达式求值struct node *calcolate(struct node *s)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=top;top=p;i=n-1;elseif(string2i=#)/遇#号结束标志

11、，输出栈中的最后计算结果printf(计算结果为:%dn,top-num);elseif(string2i=)p=(struct node *)malloc(sizeof(struct node );else y=top-nu m;p=top;top=top-n ext;free(p);x=top-nu m;p=top;top=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=top;top=p;break;case -:a=x

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

13、;top=l ni tializatio n(); 建立一个链栈，并返回栈顶指针printf(请输入表达式：n);gets(stri ng1);if(Searchexpressio n(stri ng1)head=assort(top);/中缀转化为后缀表达式calcolate(head);2、完整函数#i nclude#i nclude#i ncludevstri ng.h#i nclude#defi ne MAX 60#define RIGHT 1#defi ne WRONG 0#defi ne DEMAX 15#defi ne NULL 0char stri ng1MAX;char st

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

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

16、=strle n(stri ng1);for(i=0;i=m;i+)a=stri ng1i;if(Ov=stri ng1i&stri ng1idata=a;p-n ext=top;top=p;break;case /:strin g2j= ;j+;if(top-data=*)|(top-data=/)a=stri ng1i;string2j=top-data;j+;/比其咼，现将栈顶运算符出栈，再进栈top-data=a;break;elsep=(struct node *)malloc(sizeof(struct no de);/进栈p-data=a;p-n ext=top;top=

17、p;break;case +:case -:stri ng2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=7)stri ng2j=top-data;j+;top-data=a;break;否，直接else p=(struct node *)malloc(sizeof(struct no de);p-data=a;p-n ext=top;top=p;break;case ):stri ng2j= ;j+;if(top-data=)pri ntf(i nput error);break;while(top-data!=()stri ng2j

18、=top-data;j+;p=top;top=top-n ext;free(p); p=top;top=top-n ext;free(p);prin tf(n );break;while(top-data!=)stri ng2j=top-data;j+;p=top;top=top-n ext;free(p);strin g2j=#;printf(后缀表达式为:);for(i=0;inum);struct node *calcolate(struct node *s) struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向栈顶的指针for(

19、i=0;i=0&stri ng2iv=9)q=&stri ng2i;a=atoi(q);for(n=i;stri ng2 n=0&stri ng2 nnum=a;p-n ext=top;top=p;i=n-1;elseif(string2i=#)/遇#号结束标志，输出栈中的最后计算结果else/计算表达式的值printf(ERROR:除数为零!n);if(stri ng2i= ) else y=top-nu m;p=top;top=top-n ext;free(p);x=top-nu m;p=top;top=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=top;top=p;break;case -:a=x-y;p=(struct node *)