《数据结构实验报告表达式求值.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告表达式求值.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验报告题目： 编制一个表达式求值的程序。一 需求分析1. 本演示程序中，利用堆栈存储结构存储读入的运算符，输入的限定范围是数字（09），以及+*/()。输入字符串限定长度为20，可以根据需要进行改变。如果遇到不是以上范围或者连续输入两个运算符，如：+，则会提示输入错误，请重新输入。输出的结果是转换后的后序表达式，以及float型数字，不会含有非法字符。2. 演示程序采用的是文件输入，只需要在源代码中输入要输入的文件的地址，然后就可以在文本文件中进行输入，运行过程中会自动读取，输出文本输入的表达式，及运算结果。3. 程序执行的命令包括：1） 构造字符优先级比较表，比较优先关系 2）文件
2、输入 3）构造堆栈，运算符入栈4）堆栈输出，变为后序表达式，并计算 5）输出结果，结束4.测试数据 文件地址：C:UserslenovoDesktop4.txt 1) 输入：(35+20/2)*2-4/2+12正确输出结果是：100.00002)输入：(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=
3、|ai-1,aiD基本操作：Init stack（&s）操作结果：构造一个空的堆栈sPush stack（&s, e）初始条件：存在堆栈s操作结果:元素e压入堆栈s，top+1Pop （&s，e）初始条件：栈s已经存在且非空操作结果：删除栈顶元素e，输出其值，top-12. 程序包含三个模块：1） 运算符优先关系模块2） 主程序模块; Int main(void)初始化；Do 接受命令；处理命令；while（“命令”=”退出”）；3）堆栈模块三详细设计1.程序源代码解释为：float Result(int c,float r,int top) /定义输出结果 int j; float temp
4、; switch(c) /以下是四种基本运算的计算定义，运算完成后直接将top-1值赋予top case 42:rtop-1=rtop-1*rtop;top=top-1;break; /乘法 case 43:rtop-1=rtop-1+rtop;top=top-1;break;/加法 case 45:rtop-1=rtop-1-rtop;top=top-1;break;/减法 case 47:rtop-1=rtop-1/rtop;top=top-1;break;/ 除法 case 94:for(j=1,temp=rtop-1;j=1) /栈不空的时候，栈中元素赋给houzhi，并计数 biao
5、zhib+=i; houzhii=duizhantop-1; top=top-1;i=i+1; max=i; /从0到i循环输出后序表达式for(i=0,b=0;imax;i+) if(i!=biaozhib)printf(%d ,houzhii) ; /输出后序表达式中的数字 else printf(%c ,houzhii); /输出后序表达式中的运算符 b=b+1; top=-1;for(i=0,b=0;imax;i+) /从0到max if(i!=biaozhib) top=top+1; resulttop=houzhii; /将后值赋予result，调用result函数，进行Resul
6、t运算 else Result(houzhii,result,top); /运算结束，输出栈顶值，既是运算结果 top-; b=b+1; printf(nnThe result is %f ,Result(houzhii,result,top); /输出并打印结果 getch();return 0;/返回02.程序的模块调用：主程序文件打开读入字符输入字符有效及优先级的判断运算模块输出结果四.调试分析1. 本次作业的核心就是利用堆栈将中序表达式改成后序表达式，然后进行表达式的求值。具体思想就是当读入数字时，直接输出。当读入运算符时如果不是后括号，直接将其进栈，顺序比较读入的运算符与栈顶元素的优
7、先级（栈不空），如果栈顶元素的优先级高，则直接将其出栈并输出。遇到后括号直接输出栈中元素，直到遇到前括号。2. 算法的思想不是很复杂，在编程中只是加入了运算符的优先级比较表。以及如何获得优先级的大小关系。起初在开始编制运算符优先级比较时，完全没有想法，最后在网上学习了一下，终于学会了如何建立比较表，通过练习也加深了对堆栈的掌握。总的过程还是可以的。3. 本题中也就只使用一堆栈存储运算符，空间复杂度O与输入的表达式中的运算符的多少有关，所以空间复杂度为O（n）(其实要小一点)，对于时间复杂度而言，不仅要考虑读入表达式的时间，还要考虑优先级的比较，进出栈，虽然比较多比较复杂，但是应该也是T（n）的
8、数量级。4. 只是在WINTC下编译运行了程序 ，并把直接运行时输入改为了由文本文档文件输入，在进行改编的过程中，由于关闭文件的指针放的位置不对，还导致了输出结果始终是0，通过改变指针的位置最终完成了文件输入的改编。五心得体会 在本次实验中，我负责表达式的输出程序的编程，编写了一个result函数来进行结果输出。编程中遇到了很多困难，我们三个人也进行了很多次的讨论，遇到无法解决的困难，则寻求其他大学同学的帮助。在商讨算法的过程中，放弃了二叉树的思想，改用堆栈的方式。由于我们大一学过C语言，其函数调用简单方便，并且编写小的程序非常方便，所以选择了WIN-TC。六源代码#include Stdio
9、.h#include ctype.hint find(char x) int i; char a7=+-*/(); for(i=0;i+) if(ai!=x&i7)continue; else if(i, , , , , , ,; return(relatfind(c1)-1find(c2)-1); float Result(int c,float r,int top) int j; float temp; switch(c) case 42:rtop-1=rtop-1*rtop;top=top-1;break; case 43:rtop-1=rtop-1+rtop;top=top-1;bre
10、ak; case 45:rtop-1=rtop-1-rtop;top=top-1;break; case 47:rtop-1=rtop-1/rtop;top=top-1;break; case 94:for(j=1,temp=rtop-1;jrtop;j+) temp=rtop-1*temp; rtop-1=temp; top=top-1; break; return(rtop);int transe(char c,int len) int sum=0,i,j,temp; for(i=0;ilen;i+) for(j=0,temp=1;jlen-1-i;j+) temp=temp*10; su
11、m=sum+(ci-0)*temp; return(sum); Int main(void)char s20,duizhan20,temp10 ; float result10;int houzhi20=0,biaozhi10=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=str
12、len(s);for(j=0;jn-1;j+) if(!isdigit(sj)&!isdigit(sj+1)&sj!=(&sj+1!=(&sj!=)&sj+1!=) printf(Eeeor input!nPress any key to continue!); else continue; done=2; if(done!=2)for(j=0;jn;) if(isdigit(sj) m=0; cont=1; tempm+=sj+; done=0; while(isdigit(sj)&jn) tempm+=sj+; done=1; cont+; if(done=1) houzhii+=tran
13、se(temp,cont); else houzhii+=sj-1-0; else if(find(sj)!=7&(find(sj)!=0) if(top=0)duizhantop+=sj+; else done=0; while(done=0) switch(Compare(duizhantop-1,sj) case :biaozhib+=i; houzhii=duizhantop-1; top=top-1; if(top=0)duizhantop=sj; top=top+1;j+; done=1; i=i+1; break; else if(find(sj)=7) while(duizha
14、ntop-1!=() biaozhib+=i; top=top-1; houzhii=duizhantop; i=i+1; top=top-1; j+; else printf(Eeeor input!nPress any key to continue!); temp1=1; break; if(temp1!=1)while(top=1) biaozhib+=i; houzhii=duizhantop-1; top=top-1;i=i+1; max=i; for(i=0,b=0;imax;i+) if(i!=biaozhib)printf(%d ,houzhii) ; else printf
15、(%c ,houzhii); b=b+1; top=-1;for(i=0,b=0;imax;i+) if(i!=biaozhib) top=top+1; resulttop=houzhii; else Result(houzhii,result,top); top-; b=b+1; printf(nnThe result is %f ,Result(houzhii,result,top); getch();return 0;1.本程序的运行环境是WINTC，也可以是DOS操作系统，执行文件是*.exe。2.文件的输入直接是通过文本文档，或其他，直接在源代码中输入打开文件的地址，然后操作均在文本中进行，比较方便。界面如下：源代码中地址输入：运行中界面：七测试结果1.输入正确的表达式：(24/2+124/2)+25/5*22.输入：(32+1/3+14)*2+32/23.输入字母，非法字符：ad+12xg4.输入连续的运算符：23+12