首页 数据结构算术表达式求值实验报告

数据结构算术表达式求值实验报告

数据结构算术表达式求值实验报告数据结构算术表达式求值实验报告数据结构算术表达式求值实验报告数据结构算术表达式求值实验报告北京理工大学珠海学院《数据结构》课程设计报告题目：____________算术表达式求值_________________所在学院：专业班级：学生姓名：指导教师：2010年05月26日目录1．序言········································12．纲要设计········································12.1数据结构设计····················...

数据结构算术表达式求值实验报告数据结构算术表达式求值实验报告数据结构算术表达式求值实验报告北京理工大学珠海学院《数据结构》课程设计报告题目：____________算术表达式求值_________________所在学院：专业班级：学生姓名：指导教师：2010年05月26日目录 1．序言········································12．纲要设计········································12.1数据结构设计··············································································································12.2算法设计····················································································································12.3ADT描绘···················································································································22.4功能模块剖析··············································································································23．详尽设计········································33.1数据存储结构设计········································································································33.2主要算法流程图（或算法伪代码）····················································································34．软件测试········································65．心得领会········································8参照文件··········································8附录············································81．序言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符拥有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈协助剖析算符优先关系。在读入表达式的字符序列的同时，达成运算符和运算数的辨别办理，以及相应运算。2．纲要设计2.1数据结构设计任何一个表达式都是由操作符，运算符和界线符组成的。我们分别用次序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。次序栈的存储结构是利用一组连续的存储单元依次寄存自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在次序栈中的地点，base为栈底指针，在次序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。2.2算法设计为了实现算符优先算法。能够使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式开端符”#”为运算符栈的栈底元素；2.依次读入表达式，假如操作符即进OPND栈，假如运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完成（即OPTR栈的栈顶元素和目前读入的字符均为”#”）。2.3ADT描绘ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,，n,n≧0}数据对象：R1={|ai1,aiD,i=2,，n}约定an端为栈顶，ai端为栈底。基本操作：InitStack(&S)操作结果：结构一个空栈S。GetTop(S)初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push(&S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop(&S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1,c2)初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack2.4功能模块剖析1.栈的基本功能。InitStack(Stack*s)和InitStack2(Stack2*s)分别结构运算符栈与结构操作数栈，Push(Stack*s,charch)运算符栈插入ch为新的栈顶元素，Push2(Stack2*s,intch)操作数栈插入ch为新的栈顶元素，Pop(Stack*s)删除运算符栈s的栈顶元素，用p返回其值，Pop2(Stack2*s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stacks)用p返回运算符栈s的栈顶元素，GetTop2(Stack2s)用p返回操作数栈的栈顶元素。2.其余功能剖析。(1)In(charch)判断字符是否是运算符功能，运算符即返回1，该功能只要简单的一条语句即可实现，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。(2)Precede(charc1,charc2)判断运算符优先权功能，该函数判断运算符c1,c2的优先权，详细优先关系参照表1。Operate(inta,charop,intb)操作数用对应的运算符进行运算功能。运算结果直接返回。num(intn)求操作数的长度功能，需要用itoa函数把int型变换成字符串型，strlen函数可求字符长度。(5)EvalExpr()主要操作函数运算功能。剖析详尽见“3.详尽设计3.2”。3．详尽设计3.1数据存储结构设计因为表达式是由操作符，运算符和界线符组成的。如果只用一个char种类栈，不能知足2位以上的整数，所以还需要定义一个int种类的栈用来寄存操作数。/*定义字符种类栈*/typedefstruct{intstacksize;char*base;char*top;}Stack;/*定义整型栈*/typedefstruct{intstacksize;int*base;int*top;}Stack2;3.2主要算法流程图（或算法伪代码）Precede(charc1,charc2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+><<<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=表1算法伪代码如下：charPrecede(charc1,charc2){staticchararray[49]={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','!','>','>','>','>','!','>','>','<','<','<','<','<','!','='};//用一维数组存储49种情况switch(c1){/*i为下面array的横标*/case'+':i=0;break;case'-':i=1;break;case'*':i=2;break;case'/':i=3;break;case'(':i=4;break;case')':i=5;break;case'#':i=6;break;}switch(c2){/*j为下面array的纵标*/case'+':j=0;break;case'-':j=1;break;case'*':j=2;break;case'/':j=3;break;case'(':j=4;break;case')':j=5;break;case'#':j=6;break;}return(array[7*i+j]);/*返回运算符array[7*i+j]为对应的c1,c2优先关系*/}intEvalExpr()主要操作函数。算法纲要流程图：利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#Push(OPND,’3’)2#3*(7-2)#Push(OPTR,’*’)3#*3(7-2)#Push(OPNR,’(’)4#*(37-2)#Push(OPND,’7’)5#*(37-2)#Push(OPNR,’-’)6#*(-372)#Push(OPND,’2’)7#*(-372)#Operate(‘7’,’-’,’2’)8#*(35)#Pop(OPTR)9#*35#Operate(‘3’,’*’,5’)10#15#Return(GetTop2(OPND))表2算法伪代码如下：intEvalExpr()//主要操作函数{c=*ptr++;while(c!='#'||GetTop(OPTR)!='#'){if(!In(c))//不是运算符即进栈{if(!In(*(ptr-1)))ptr=ptr-1;m=atoi(ptr);//取字符串前面的数字段n=num(m);Push2(&OPND,m);ptr=ptr+n;c=*ptr++;}elseswitch(Precede(GetTop(OPTR),c)){case'<'://栈顶元素优先权底Push(&OPTR,c);c=*ptr++;break;case'='://脱括号并接收下一字符x=Pop(&OPTR);c=*ptr++;break;case'>'://退栈并将运算结果入栈theta=Pop(&OPTR);b=Pop2(&OPND);a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break;}}4．软件测试运行成功后界面。输入正确的表达式后。3.更改表达式，输入有2位数的整数调试。5．心得领会这次课程设计让我更为认识大一学到的C和这个学期学到的数据结构。课设题目要求不单要求对课本知识有较深刻的认识，同时要求程序设计者有较强的思维和着手能力和更为认识编程思想和编程技巧。这次课程设计让我有一个深刻的领会，那就是细节决定成败，编程最需要的是谨慎，怎样的谨慎都可是分，往往检查了半天发现错误发生在某个括号，分号，引号，或许数据种类上。就像我在写EvalExpr()函数时，忘了指针的地点符值不用加*号，这一点小小的错误也耽搁了我几十分钟，所以说细节很重要。程序设计时，也不要怕碰到错误，在实际操作过程中犯的一些错误还会存心外的收获，感觉课程设计很存心思。在详细操作中这学期所学的数据结构的理论知识获得稳固，达到课程设计的基本目的，也发现自己的不足之出，在此后的上机中应更为注意，同时领会到语言拥有的语句简短，使用灵活，履行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。这个程序是我们3个人达成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须弘扬团结协作的精神。某个人的离群都可能致使致使整项工作的失败。实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能致使整个工作失败。团结协作是我们成功的一项特别重要的保证。而这次课程设计也正好锻炼我们这一点，这也是特别可贵的最后，感谢老师在这次课程设计的尽心指导，祝老师身体健康，工作顺利。参照文件：1.《数据结构(C语言版)》严蔚敏清华大学出版社2.《C语言程序设计》丁峻岭中国铁道出版社3.《C程序设计》谭浩强清华大学出版社附录程序源代码：#include#include#include#defineNULL0#defineOK1#defineERROR-1#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT20/*定义字符种类栈*/typedefstruct{intstacksize;char*base;char*top;}Stack;/*定义整型栈*/typedefstruct{intstacksize;int*base;int*top;}Stack2;/*-----------------全局变量---------------*/StackOPTR;/*定义运算符栈*/Stack2OPND;/*定义操作数栈*/charexpr[255]="";/*寄存表达式串*/char*ptr=expr;intInitStack(Stack*s)//结构运算符栈{s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!s->base)returnERROR;s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}intInitStack2(Stack2*s)//结构操作数栈{s->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s->base)returnERROR;s->stacksize=STACK_INIT_SIZE;s->top=s->base;returnOK;}intIn(charch)//判断字符是否是运算符，运算符即返回1{return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');}intPush(Stack*s,charch)//运算符栈插入ch为新的栈顶元素{*s->top=ch;s->top++;return0;}intPush2(Stack2*s,intch)//操作数栈插入ch为新的栈顶元素{*s->top=ch;s->top++;return0;}charPop(Stack*s)//删除运算符栈s的栈顶元素，用p返回其值{charp;s->top--;p=*s->top;returnp;}intPop2(Stack2*s)//删除操作数栈s的栈顶元素，用p返回其值{s->top--;p=*s->top;returnp;}charGetTop(Stacks)//用p返回运算符栈s的栈顶元素{charp=*(s.top-1);returnp;}intGetTop2(Stack2s)//用p返回操作数栈s的栈顶元素{intp=*(s.top-1);returnp;}/*判断运算符优先权，返回优先权高的*/charPrecede(charc1,charc2){inti=0,j=0;staticchararray[49]={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','!','>','>','>','>','!','>','>','<','<','<','<','<','!','='};switch(c1){/*i为下面array的横标*/case'+':i=0;break;case'-':i=1;break;case'*':i=2;break;case'/':i=3;break;case'(':i=4;break;case')':i=5;break;case'#':i=6;break;}switch(c2){/*j为下面array的纵标*/case'+':j=0;break;case'-':j=1;break;case'*':j=2;break;case'/':j=3;break;case'(':j=4;break;case')':j=5;break;case'#':j=6;break;}return(array[7*i+j]);/*返回运算符*/}/*操作函数*/intOperate(inta,charop,intb){switch(op){case'+':return(a+b);case'-':return(a-b);case'*':return(a*b);case'/':return(a/b);}return0;}intnum(intn)//返回操作数的长度{charp[10];itoa(n,p,10);//把整型变换成字符串型n=strlen(p);returnn;}intEvalExpr()//主要操作函数{charc,theta,x;intn,m;inta,b;c=*ptr++;while(c!='#'||GetTop(OPTR)!='#'){if(!In(c)){if(!In(*(ptr-1)))ptr=ptr-1;m=atoi(ptr);//取字符串前面的数字段n=num(m);Push2(&OPND,m);ptr=ptr+n;c=*ptr++;}elseswitch(Precede(GetTop(OPTR),c)){case'<':Push(&OPTR,c);c=*ptr++;break;case'=':x=Pop(&OPTR);c=*ptr++;break;case'>':theta=Pop(&OPTR);b=Pop2(&OPND);a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break;}}returnGetTop2(OPND);}intmain(){printf("请输入正确的表达式以'#'结尾:");do{gets(expr);}while(!*expr);InitStack(&OPTR);/*初始化运算符栈*/Push(&OPTR,'#');/*将#压入运算符栈*/InitStack2(&OPND);/*初始化操作数栈*/printf("表达式结果为:%d\n",EvalExpr());return0;}课程设计成绩评定表教师评语1、课程设计表现：2、程序、软件质量：3、设计报告质量：4、辩论表现：5、独到的看法、方法与创新性：6、总结：成绩记录平时成绩（10分）程序检查（20+20分）设计报告文档（20分）课程设计辩论（20+10分）最后（百分）成绩成绩（等级）评定

                    本文档为【数据结构算术表达式求值实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构算术表达式求值实验报告

你可能还喜欢