将中缀表达式转换为后缀表达式并计算.docx
- 文档编号:12942422
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:20
- 大小:18.70KB
将中缀表达式转换为后缀表达式并计算.docx
《将中缀表达式转换为后缀表达式并计算.docx》由会员分享,可在线阅读,更多相关《将中缀表达式转换为后缀表达式并计算.docx(20页珍藏版)》请在冰点文库上搜索。
将中缀表达式转换为后缀表达式并计算
《数据结构》实验报告
◎实验题目:
使用键盘输入表达式,计算表达式的值并输出;将表达式转化成后缀表达式输出,利用后缀表达式求表达式的值并输出。
◎实验目的:
使用栈的操作编写关于数据结构的程序。
◎实验内容:
写出程序并上机调试、通过。
一、需求分析
1、演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“请输入表达式”时输入中缀表达式。
然后计算机终端输出转换后的后缀表达式及计算后的结果。
2、程序执行的命令包括:
(1)构造链栈;
(2)输入数据;(3)判断输入的表达式是否为非法表达式;(4)将中缀表达式转换为后缀表达式;(5)计算表达式的值;(6)输出。
(7)结束
4、本程序能将中缀表达式转换为后缀表达式,并且能计算表达式的值。
5、输入及输出示例:
例1:
请输入表达式
6+3*(6+5)
后缀表达式:
6365+*+
计算结果为:
39
Pressanykeytocontinue
例2:
请输入表达式
6-3*(7+1
ERROR:
表达式错误
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、每个模块:
(1)定义结构体
structnode
{
chardata;
intnum;
structnode*next;
};
(2)判断表达式是否非法
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++;
else
if(string1[i1]==')')
b2++;
}
if(b1!
=b2)
{printf("ERROR:
缺少括号\n");return(WRONG);}
for(i1=0;i1 if('0'<=string1[i1]&&string1[i1]<='9'&&'0'<=string1[i1+1]&&string1[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);} else if(string1[i1]=='-'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/')) {printf("ERROR: 表达式缺操作数! \n");return(WRONG);} else if(string1[i1]=='*'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/')) {printf("ERROR: 表达式缺操作数! \n");return(WRONG);} else if(string1[i1]=='/'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[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 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; } else if(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 #include #include #include #defineMAX60 #defineRIGHT1 #defineWRONG0 #defineDEMAX15 #defineNULL0 charstring1[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++; else if(string1[i1]==')') b2++; } if(b1! =b2) {printf("ERROR: 缺少括号\n");return(WRONG);} for(i1=0;i1 if('0'<=string1[i1]&&string1[i1]<='9'&&'0'<=string1[i1+1]&&string1[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);} else if(string1[i1]=='-'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/')) {printf("ERROR: 表达式缺操作数! \n");return(WRONG);} else if(string1[i1]=='*'&&(string1[i1+1]=='+'||string1[i1+1]=='-'||string1[i1+1]=='*'||string1[i1+1]=='/')) {printf("ERROR: 表达式缺操作数! \n");return(WRONG);} else if(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 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; } else if(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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中缀 表达式 转换 后缀 计算