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

.《数据结构》实验报告◎实验题目:使用键盘输入表达式，计算表达式的值并输出；将表达式转化成后精品文档放心下载缀表达式输出，利用后缀表达式求表达式的值并输出。◎实验目的：使用栈的操作编写关于数据结构的程序。◎实验内容：写出程序并上机调试、通过。一、需求分析1、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“请输入表达式”时输入中缀表达式。然后计算机终端输出转换后的后缀表达式及计算后的结果。感谢阅读2、程序执行的命令包括：（1）构造链栈；（2）输入数据；（3）判断输入的表达式是否为非法表达式；（4）将中缀表达式转换为后缀表达式；（5）计算表达式的值；（6）输出。（7）结束感谢阅读4、本程序能将中缀表达式转换为后缀表达式，并且能计算表达式的值。精品文档放心下载5、输入及输出示例：1：请输入表达式.6+3*（6+5）后缀表达式：6365+*+计算结果为：39Pressanykeytocontinue例2：请输入表达式6-3*（7+1ERROR:表达式错误Pressanykeytocontinue二概要设计1．基本操作(1)、structnode操作结果：创建结构体(2)、intSearchexpression(charstring1[])谢谢阅读初始条件：表达式string1已经存在。操作结果：判断表达式是否非法(3)、structnode*Initialization()谢谢阅读操作结果：创建栈链。(4)、structnode*assort(structnode*s)谢谢阅读初始条件：string1、string2已存在。操作结果：将中缀表达式转换为后缀表达式并存在string2中。谢谢阅读(5)、structnode*calcolate(structnode*s)谢谢阅读.操作结果：求出表达式的值2、模块调用图主程序模块创建结构体判断表达式是否非法将中缀表达式转换为后缀表达式表达式求值三详细设计1、每个模块：定义结构体structnode{chardata;intnum;structnode*next;};判断表达式是否非法intSearchexpression(charstring1[])精品文档放心下载{.inti1,b1,b2;intm;m=strlen(string1);if(string1[0]<'0'||string1[0]>'9')感谢阅读{printf("ERROR:表达式缺操作数！\n");return(WRONG);谢谢阅读}for(i1=0;i1<=m;i1++){if(string1[i1]=='(')b1++;elseif(string1[i1]==')')b2++;}if(b1!=b2){printf("ERROR:缺少括号\n");return(WRONG);}感谢阅读for(i1=0;i1<m;i1++)if('0'<=string1[i1]&&string1[i1]<='9'&&'0'<=string1[i1+1]&&str精品文档放心下载ing1[i1+1]<='9'){printf("ERROR:表达式缺操作符！\n");return(WRONG);}精品文档放心下载.for(i1=0;i1<=m;i1++)if(string1[i1]=='+'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/'))谢谢阅读{printf("ERROR:表达式缺操作数！\n");return(WRONG);}精品文档放心下载elseif(string1[i1]=='-'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/'))精品文档放心下载{printf("ERROR:表达式缺操作数！\n");return(WRONG);}感谢阅读elseif(string1[i1]=='*'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/'))谢谢阅读{printf("ERROR: 表 达 式 缺 操 作 数 ！感谢阅读\n");return(WRONG);}elseif(string1[i1]=='/'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||strin感谢阅读.g1[i1+1]=='*'||string1[i1+1]=='/'))感谢阅读{printf("ERROR: 表 达 式 缺 操 作 数 ！精品文档放心下载\n");return(WRONG);}return(RIGHT);}(3)、将中缀表达式转换为后缀表达式structnode*assort(structnode*s)//输入字符串谢谢阅读{structnode*p,*top;inti;top=s;intm;chara;m=strlen(string1);for(i=0;i<=m;i++){a=string1[i];if('0'<=string1[i]&&string1[i]<='9')谢谢阅读{string2[j]=string1[i];j++;谢谢阅读.}else{switch(a){case'(':{p=(structnode*)malloc(sizeof(structnode));谢谢阅读p->data=a;p->next=top;top=p;break;}case'*':case'/':string2[j]='';j++;if((top->data=='*')||(top->data=='/'))谢谢阅读{string2[j]=top->data;j++;//比其高，现将栈顶运算符感谢阅读出栈，再进栈。top->data=a;break;}else.{p=(structnode*)malloc(sizeof(structnode));//否，精品文档放心下载直接进栈p->data=a;p->next=top;top=p;break;}case'+':case'-':{string2[j]='';j++;if(top->data=='+'||top->data=='-'||top->data=='*'||top->data=感谢阅读='/'){string2[j]=top->data;j++;top->data=a;break;}else{p=(structnode*)malloc(sizeof(structnode));精品文档放心下载.p->data=a;p->next=top;top=p;break;}}case')':{string2[j]='';j++;if(top->data=='@'){printf("inputerror");break;}谢谢阅读while(top->data!='('){string2[j]=top->data;j++;p=top;top=top->next;free(p);}p=top;top=top->next;free(p);谢谢阅读break;}}.}}while(top->data!='@'){string2[j]=top->data;j++;p=top;top=top->next;free(p);}string2[j]='#';printf("后缀表达式为:");for(i=0;i<j;i++)if(string2[i]!='')printf("%c",string2[i]);printf("\n");returntop;}(4)表达式求值structnode*calcolate(structnode*s)谢谢阅读{structnode*top,*p;.char*q;intx,y,a;inti,n;top=s;//指向栈顶的指针for(i=0;i<=j;i++)//遍历字符串string2精品文档放心下载{if(string2[i]>='0'&&string2[i]<='9')精品文档放心下载{q=&string2[i];a=atoi(q);for(n=i;string2[n]>='0'&&string2[n]<='9';n++){}p=(structnode*)malloc(sizeof(structnode));p->num=a;p->next=top;top=p;i=n-1;精品文档放心下载}elseif(string2[i]=='#') //遇#号结束标志，输出栈中的最后计算精品文档放心下载结果printf("计算结果为:%d\n",top->num);精品文档放心下载else{if(string2[i]==''){}.else{y=top->num;p=top;top=top->next;free(p);谢谢阅读x=top->num;p=top;top=top->next;free(p);谢谢阅读switch(string2[i]){case'+':{a=x+y;p=(structnode*)malloc(sizeof(structnode));p->num=a;p->next=top;top=p;break;}谢谢阅读case'-':{a=x-y;p=(structnode*)malloc(sizeof(structnode));p->num=a;p->next=top;top=p;break;}谢谢阅读case'*':{a=x*y;p=(structnode*)malloc(sizeof(structnode));p->num=a;p->next=top;top=p;break;}精品文档放心下载case'/':{if(y==0)printf("ERROR:除数为零!\n");a=(float)x/y;p=(structnode*)malloc(sizeof(structnode));p->num=a;p->next=top;top=p;精品文档放心下载.break;}}}}}return0;}(5)、主函数voidmain(){structnode*top,*head;top=Initialization();//建立一个链栈，并返回栈顶指针感谢阅读printf("请输入表达式：\n");gets(string1);if(Searchexpression(string1))谢谢阅读{head=assort(top);//中缀转化为后缀表达式精品文档放心下载calcolate(head);}}2、完整函数#include<stdio.h>.#include<malloc.h>#include<string.h>#include<stdlib.h>#defineMAX60#defineRIGHT1#defineWRONG0#defineDEMAX15#defineNULL0charstring1[MAX];charstring2[MAX];intj=0;structnode//定义结构体。{chardata;intnum;structnode*next;};intSearchexpression(charstring1[]) //判断非法表达式谢谢阅读{inti1,b1,b2;intm;m=strlen(string1);.if(string1[0]<'0'||string1[0]>'9')谢谢阅读{printf("ERROR:表达式缺操作数！\n");return(WRONG);谢谢阅读}for(i1=0;i1<=m;i1++){if(string1[i1]=='(')b1++;elseif(string1[i1]==')')b2++;}if(b1!=b2){printf("ERROR:缺少括号\n");return(WRONG);}感谢阅读for(i1=0;i1<m;i1++)if('0'<=string1[i1]&&string1[i1]<='9'&&'0'<=string1[i1+1]&&string谢谢阅读1[i1+1]<='9'){printf("ERROR:表达式缺操作符！\n");return(WRONG);}for(i1=0;i1<=m;i1++)精品文档放心下载if(string1[i1]=='+'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[谢谢阅读.i1+1]=='*'||string1[i1+1]=='/'))谢谢阅读{printf("ERROR:表达式缺操作数！\n");return(WRONG);}感谢阅读elseif(string1[i1]=='-'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/'))谢谢阅读{printf("ERROR:表达式缺操作数！\n");return(WRONG);}谢谢阅读elseif(string1[i1]=='*'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/'))感谢阅读{printf("ERROR:表达式缺操作数！\n");return(WRONG);}谢谢阅读elseif(string1[i1]=='/'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/'))感谢阅读{printf("ERROR: 表 达 式 缺 操 作 数 ！精品文档放心下载\n");return(WRONG);}.return(RIGHT);}structnode*Initialization()//初始化栈链,链栈不带头结点谢谢阅读{structnode*top;top=(structnode*)malloc(sizeof(structnode));精品文档放心下载top->data='@';top->num=0;top->next=NULL;returntop;}structnode*assort(structnode*s)//输入字符串谢谢阅读{structnode*p,*top;inti;top=s;intm;chara;m=strlen(string1);for(i=0;i<=m;i++).{a=string1[i];if('0'<=string1[i]&&string1[i]<='9')谢谢阅读{string2[j]=string1[i];j++;谢谢阅读}else{switch(a){case'(':{p=(structnode*)malloc(sizeof(structnode));谢谢阅读p->data=a;p->next=top;top=p;break;}case'*':case'/':string2[j]='';j++;if((top->data=='*')||(top->data=='/'))感谢阅读{string2[j]=top->data;j++;//比其高，现将栈顶运算符出感谢阅读.栈，再进栈。top->data=a;break;}else{p=(structnode*)malloc(sizeof(structnode));//否，直接感谢阅读进栈p->data=a;p->next=top;top=p;break;}case'+':case'-':{string2[j]='';j++;if(top->data=='+'||top->data=='-'||top->data=='*'||top->data=='/')感谢阅读{string2[j]=top->data;j++;top->data=a;break;.}else{p=(structnode*)malloc(sizeof(structnode));p->data=a;p->next=top;top=p;精品文档放心下载break;}}case')':{string2[j]='';j++;if(top->data=='@'){printf("inputerror");break;}精品文档放心下载while(top->data!='('){string2[j]=top->data;j++;p=top;top=top->next;free(p);}p=top;top=top->next;free(p);感谢阅读.break;}}}}while(top->data!='@'){string2[j]=top->data;j++;p=top;top=top->next;free(p);}string2[j]='#';printf("后缀表达式为:");for(i=0;i<j;i++)if(string2[i]!='')printf("%c",string2[i]);printf("\n");returntop;}.structnode*calcolate(structnode*s) //计算表达式的值感谢阅读{structnode*top,*p;char*q;intx,y,a;inti,n;top=s;//指向栈顶的指针for(i=0;i<=j;i++)//遍历字符串string2感谢阅读{if(string2[i]>='0'&&string2[i]<='9')感谢阅读{q=&string2[i];a=atoi(q);for(n=i;string2[n]>='0'&&string2[n]<='9';n++){}p=(structnode*)malloc(sizeof(structnode));p->num=a;p->next=top;top=p;i=n-1;感谢阅读}elseif(string2[i]=='#') //遇#号结束标志，输出栈中的最后计算结果精品文档放心下载printf("计算结果为:%d\n",top->num);谢谢阅读else.{if(string2[i]==''){}else{y=top->num;p=top;top=top->next;free(p);精品文档放心下载x=top->num;p=top;top=top->next;free(p);谢谢阅读switch(string2[i