语言数据结构实验报告表达式的转换.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;i1if（'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;iif（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;i1if（'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;iif（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;
升级会员 