数据结构实验报告表达式求值_数据结构实验报告范例
数据结构实验报告表达式求值由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告范例”。
数据结构实验报告
题目：
编制一个表达式求值的程序。
一． 需求分析
1.本演示程序中，利用堆栈存储结构存储读入的运算符，输入的限定范围是数字（0—9），以及+*/()。输入字符串限定长度为20，可以根据需要进行改变。如果遇到不是以上范围或者连续输入两个运算符，如：++，则会提示输入错误，请重新输入。输出的结果是转换后的后序表达式，以及float型数字，不会含有非法字符。
2.演示程序采用的是文件输入，只需要在源代码中输入要输入的文件的地址，然后就可以在文本文件中进行输入，运行过程中会自动读取，输出文本输入的表达式，及运算结果。3.程序执行的命令包括：
1）构造字符优先级比较表，比较优先关系 2）文件输入 3）构造堆栈，运算符入栈 4）堆栈输出，变为后序表达式，并计算 5）输出结果，结束 4.测试数据
文件地址：C:UserslenovoDesktop4.txt
1)输入：(35+20/2)*2-4/2+12 正确输出结果是：100.0000 2)输入：(35+20/2)*2-/2+12 结果是:error input
3)输入：a+ar/3=135 结果是:error input
二．概要设计
为实现以上程序功能，需运用堆栈用于存储运算符，因此需要定义抽象数据类型。1.堆栈的抽象数据类型定义为: ADT stack｛
数据对象:D={ai|ai∈正整数，i=0，1，2，3，…n,及｛+-*/()｝} 数据关系：R1={|ai-1,ai∈D} 基本操作： Init stack（&s）
操作结果：构造一个空的堆栈s Push stack（&s, e）初始条件：存在堆栈s 操作结果:元素e压入堆栈s，top+1 Pop（&s，e）
初始条件：栈s已经存在且非空
操作结果：删除栈顶元素e，输出其值，top-1 2.程序包含三个模块： 1）运算符优先关系模块 2）主程序模块;Int main(void){ 初始化； Do｛
接受命令； 处理命令； ｝while（“命令”=”退出”）； ｝ 3）堆栈模块
三．详细设计
1.程序源代码解释为：
float Result(int c,float r[],int top){
//定义输出结果
int j;
float temp;
switch(c){
//以下是四种基本运算的计算定义，运算完成后直接将top-1值赋予top
case 42:r[top-1]=r[top-1]*r[top];top=top-1;break;
//乘法
case 43:r[top-1]=r[top-1]+r[top];top=top-1;break;///加法
case 45:r[top-1]=r[top-1]-r[top];top=top-1;break;//减法
case 47:r[top-1]=r[top-1]/r[top];top=top-1;break;// 除法
case 94:for(j=1,temp=r[top-1];j
temp=r[top-1]*temp;
//循环相乘
r[top-1]=temp;
top=top-1;
break;
}
return(r[top]);}
if(temp1!=1){ while(top>=1){
//栈不空的时候，栈中元素赋给houzhi，并计数
biaozhi[b++]=i;
houzhi[i]=duizhan[top-1];
top=top-1;i=i+1;
} max=i;
//从0到i循环输出后序表达式 for(i=0,b=0;i
if(i!=biaozhi[b])printf(“%d ”,houzhi[i]);
//输出后序表达式中的数字
else {
printf(“%c ”,houzhi[i]);
//输出后序表达式中的运算符
b=b+1;
}
}
top=-1;for(i=0,b=0;i
//从0到max
if(i!=biaozhi[b]){
top=top+1;
result[top]=houzhi[i];
//将后值赋予result，调用result函数，进行Result运算
}
else {Result(houzhi[i],result,top);
//运算结束，输出栈顶值，既是运算结果
top--;
b=b+1;
}
}
printf(“nnThe result is %f ”,Result(houzhi[i],result,top));
//输出并打印结果
} } getch();return 0;///返回0 } 2.程序的模块调用：
主程序 ↓
文件打开读入字符
↓
输入字符有效及优先级的判断
↓ 运算模块 ↓ 输出结果
四.调试分析
1.本次作业的核心就是利用堆栈将中序表达式改成后序表达式，然后进行表达式的求值。具体思想就是当读入数字时，直接输出。当读入运算符时如果不是后括号，直接将其进栈，顺序比较读入的运算符与栈顶元素的优先级（栈不空），如果栈顶元素的优先级高，则直接将其出栈并输出。遇到后括号直接输出栈中元素，直到遇到前括号。
2.算法的思想不是很复杂，在编程中只是加入了运算符的优先级比较表。以及如何获得优先级的大小关系。起初在开始编制运算符优先级比较时，完全没有想法，最后在网上学 习了一下，终于学会了如何建立比较表，通过练习也加深了对堆栈的掌握。总的过程还是可以的。
3.本题中也就只使用一堆栈存储运算符，空间复杂度O与输入的表达式中的运算符的多少有关，所以空间复杂度为O（n）(其实要小一点)，对于时间复杂度而言，不仅要
考虑读入表达式的时间，还要考虑优先级的比较，进出栈，虽然比较多比较复杂，但是应该也是T（n）的数量级。
4.只是在WIN—TC下编译运行了程序，并把直接运行时输入改为了由文本文档文件输入，在进行改编的过程中，由于关闭文件的指针放的位置不对，还导致了输出结果始终是0，通过改变指针的位置最终完成了文件输入的改编。
五．心得体会
在本次实验中，我负责表达式的输出程序的编程，编写了一个result函数来进行结果输出。编程中遇到了很多困难，我们三个人也进行了很多次的讨论，遇到无法解决的困难，则寻求其他大学同学的帮助。在商讨算法的过程中，放弃了二叉树的思想，改用堆栈的方式。由于我们大一学过C语言，其函数调用简单方便，并且编写小的程序非常方便，所以选择了WIN-TC。
六．源代码
#include “Stdio.h” #include “ctype.h” int find(char x){
int i;
char a[7]=“+-*/^()”;
for(i=0;;i++)
if(a[i]!=x&&i
else if(i
else return(0);
}
char Compare(char c1,char c2){
char relat[7][7]={{'>','>',''}, {'>','>',''}, {'>','>','>','>',''}, {'>','>','>','>',''}, {'>','>','>','>','>',''}, {'
{'>','>','>','>','>',' ','>'}};
return(relat[find(c1)-1][find(c2)-1]);
}
float Result(int c,float r[],int top){
int j;
float temp;
switch(c){
case 42:r[top-1]=r[top-1]*r[top];top=top-1;break;
case 43:r[top-1]=r[top-1]+r[top];top=top-1;break;
case 45:r[top-1]=r[top-1]-r[top];top=top-1;break;
case 47:r[top-1]=r[top-1]/r[top];top=top-1;break;
case 94:for(j=1,temp=r[top-1];j
temp=r[top-1]*temp;
r[top-1]=temp;
top=top-1;
break;
}
return(r[top]);}
int transe(char c[],int len){
int sum=0,i,j,temp;
for(i=0;i
for(j=0,temp=1;j
temp=temp*10;
sum=sum+(c[i]-'0')*temp;
}
return(sum);}
Int main(void){ char s[20],duizhan[20],temp[10];
float result[10];int houzhi[20]={0},biaozhi[10]={0};int i=0,j=0,m=0,top=0,b=0,done,n,temp1=0,cont,max;
FILE* fp = fopen(“C:UserslenovoDesktop4.txt”, “r”);
if(fp==NULL){printf(“cannot open filen”);
exit(0);} fscanf(fp, “%s”, s);
printf(“%sn”,s);
n=strlen(s);
for(j=0;j
if(!isdigit(s[j])&&!isdigit(s[j+1])&&s[j]!='('&&s[j+1]!='('&&s[j]!=')'&&s[j+1]!=')')
printf(“Eeeor input!nPre any key to continue!”);
else continue;
done=2;
}
if(done!=2){ for(j=0;j
if(isdigit(s[j])){
m=0;cont=1;
temp[m++]=s[j++];
done=0;
while(isdigit(s[j])&&j
temp[m++]=s[j++];
done=1;
cont++;
}
if(done==1)
houzhi[i++]=transe(temp,cont);
else houzhi[i++]=s[j-1]-'0';
}
else if(find(s[j])!=7&&(find(s[j])!=0))
{
if(top==0)duizhan[top++]=s[j++];
else{
done=0;
while(done==0){
switch(Compare(duizhan[top-1],s[j])){
case '
top=top+1;j++;
done=1;
break;
case '=':biaozhi[b++]=i;
houzhi[i]=duizhan[top-1];
top=top-1;
if(top==0){duizhan[top]=s[j];
top=top+1;j++;
done=1;
}
i=i+1;
break;
case '>':biaozhi[b++]=i;
houzhi[i]=duizhan[top-1];
top=top-1;
if(top==0){duizhan[top]=s[j];
top=top+1;j++;
done=1;
}
i=i+1;
break;
}
}
}
}
else if(find(s[j])==7){
while(duizhan[top-1]!='('){
biaozhi[b++]=i;
top=top-1;
houzhi[i]=duizhan[top];
i=i+1;
}
top=top-1;
j++;
}
else {
printf(“Eeeor input!nPre any key to continue!”);
temp1=1;
break;
} } if(temp1!=1){ while(top>=1){
biaozhi[b++]=i;
houzhi[i]=duizhan[top-1];
top=top-1;i=i+1;
} max=i;
for(i=0,b=0;i
if(i!=biaozhi[b])printf(“%d ”,houzhi[i]);
else {
printf(“%c ”,houzhi[i]);
b=b+1;
}
} top=-1;for(i=0,b=0;i
if(i!=biaozhi[b]){
top=top+1;
result[top]=houzhi[i];
}
else {Result(houzhi[i],result,top);
top--;
b=b+1;
}
}
printf(“nnThe result is %f ”,Result(houzhi[i],result,top));
} } getch();return 0;}
1.本程序的运行环境是WIN—TC，也可以是DOS操作系统，执行文件是***.exe。
2.文件的输入直接是通过文本文档，或其他，直接在源代码中输入打开文件的地址，然后操作均在文本中进行，比较方便。界面如下： 源代码中地址输入：
运行中界面：
七．测试结果
1.输入正确的表达式：(24/2+12－4/2)+25/5*2
2.输入：(32+1/3+14)*2+3^2/2
3.输入字母，非法字符：ad+12xg
4.输入连续的运算符：23++12
