表达式求值设计报告深入探索计算模型和方法.docx

1需求分析错误!未定义书签。1.1问题描述错误!未定义书签。1.2基本规定错误!未定义书签。2概要设计错误!未定义书签。1.1 数据构造错误!未定义书签。1.2 各模块间的调用关系及算法设计21.2.1 栈的抽象数据类型的定义3栈的基本功能43 详细设计63.1 数据存储构造设计63.2 主函数和其他函数的设计与实现错误!未定义书签。3.3 3函数功能分析错误!未定义书签。3.4 函数间的调用关系错误!未定义书签。4 调试与分析错误!未定义书签。4.1 程序调试错误!未定义书签。4.2 数据分析错误!未定义书签。5顾客手册错误!未定义书签。5.1 运行环境错误!未定义书签。5.2 执行文献错误!未定义书签。6参照文献错误!未定义书签。7心得体会错误!未定义书签。8小组组员任务分派及工作进度安排错误!未定义书签。1需求分析11问题描述在计算机中，算术体现式由常量、变量、运算符和括号构成。由于不一样B运算符具有不一样B优先级，又要考虑括号，因此，算术体现式的求值不也许严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一种算术体现式，由常量、变量、运算符和括号构成(以字符串形式输入)操作符为+、-*、/,用#表达结束。算法输出：体现式运算成果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入体现式H字符序列的I同步，完毕运算符和运算数B识别处理，以及对应运算。本算法B¾时间复杂度与输入B体现式B长度有亲密的关系，在此不作深入分析。12基本规定设计友好的顾客界面，运用所学工具开发一种简朴的体现式求值应用程序，该程序可以对体现式进行加、减、乘、除运算，体现式中日勺操作数规定在实数范围内；对于异常体现式应能给出错误提醒。针对前面B¾规定分别设计合理B¾测试数据，例如3.154*(12+18)-23B¾成果应当是71.62等。2概要设计2.1数据构造体现式求值是程序设计语言编译中B一种最基本B¾问题。它B实现是栈应用B¾一种经典例子。本程序使用一般使用的算法为“算符优先法”。要把一种体现式翻译成对B求值的一种机器指令序列，或者直接对求值首先要可以对的解释体现式。例如，要对下面的算术体现式求值：4+2*3-10/5首先要理解算术四则运算的规则。即：(1)先乘除，后加减；(2)从左算到右；(3)先括号内，后括号外；由此，这个算术体现式的计算次序应为4+2*3-10/5=4+6-10/5=10-10/5=10-2=8算符优先法就是根据这个运算优先关系的规定来实现对体现式的编译或解释执行的。任何一种体现式都是由操作数(operand)运算符(operator)和界线符(delimiter)构成B,我们称它们为单词。一般地操作数即可以是常数也可以是被阐明为变量或常量B标识符；运算符可以分为算术运算符、关怀运算数和逻辑运算符三类；基本界线符有左右括号和体现式结束等。这里我们仅讨论算数体现式的求值问题。这种体现式只具有加、减、乘、除四种运算符。我们把运算符和界线符统称为算符，他们构成的集合命名为0P。根据上述三条运算规则，在运算0¾每一步中，任意两个相继出现B算符OI和。2之间B优先关系至多是下面三种关系之一；KO2i日勺优先权低于O2=2OJ总优先权等于2>21的优先权高于。2表2.1定义了算符之间的优先关。表2.1算符间0优先关系+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<ZZ)>>>>>>n<<<<<ZZ2.2各模块间的调用关系及算法设计各模块间的调用关系如下图:输入体现式lIj/X体现式计算输出成果IJ图2.1模块间的调用关系为了实现算符优先算法，可以使用两个工作栈。一种称做OPTR,用以寄存运算符;另一种称做OPND,用以寄存操作数或运算成果。算法的基本思想是：(1)首先置操作数栈为空栈，体现式起始符“y为运算符的栈底元素；(2)依次读入体现式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈0¾栈顶运算符比较优先权后做对应操作，直至整个体现式求值完毕(即OPTR栈时的栈顶元素和目前读入B¾字符均为2.2.1栈的抽象数据类型的定义ADTStack数据对象：D=aaiElemSetj=1,2,n,n=0数据对象：R1=<ai-1,a>ai.1,aiD,i=2,n约定端为栈顶，ai端为栈底。InitStack(&S)操作成果：构造一种空栈S。PUSh(&S,Ch)初始条件：栈S已存在。操作成果：插入元素Ch为新B栈顶元素。Pop(&S)初始条件：栈S已存在。操作成果：删除S的栈顶元素。Priority(cl,c2)初始条件：cl,c2为运算符。操作成果：判断运算符优先权，返回优先权高的。Process(a,op,b)初始条件：a,b为实数，OP为运算符。操作成果：a与b进行运算，OP为算符，返回其值。ADTStack栈的基本功能InitNumStack(NumStack*s)和InitOPStaCk(OPStaCk*s)分别构造操作数栈与构造算符栈，PushNum(NumStack*numstack,doublenum)操作数栈插入num为新的栈顶元素，PushOp(OpStack*opstack,charop)算符栈插入OP为新的J栈顶元素，PopOp(OpStack*opstack,char*op)删除运算符栈sWj栈顶元素，用P返回其值，PopNum(NumStack*numstack,double*num)删除操作数栈SB栈顶元素，用P返回其值。其中部分操作的算法如下：voidProcess(NumStack*numstack,OpStack*opstack,charx)(根据输入0体现式求值，若体现式输入对B则返回成果，否则返回错误处理doublea,b;charc;staticdoubletempnum=0.00000000;staticintIen=IOjstaticintdot=0,flags=0;if(isdigit(x)x='.')判断输入B字符与否是09或小数点/*这段是处理数字符*/if(x=，.,)dot=l;else(if(dot0)tempnum=tempnum*10+Cint(x);/Cint将字符数转化为整数else(tempnum=tempnum+(double)Cint(x)len;len*=10;)else/*这段是处理操作符*/if(fIags=O&&x!三,OPushNum(numstack,tempnum);tempnum=0.00000000;Ien=IOjdot=O;switch(Priority(opstack->arrayopstack->top-l,x)*根据PriOrityB返回值做对应、J处理*/case,>>:PushOp(opstack,x);flags=。;break;不小于进栈case'<':不不小于出栈进行运算并把成果入栈PopOp(opstack,&c);PopNum(nunstack,&b);PopNum(numstack,&a);PushNum(numstack,Calc(a,b,c);flags=l;Process(numstack,opstack,x);break;case,=,:POPOP(OPStaCk,&c);fIags=I;break;脱括号处理default:printf(z,WrongExpress!z/);exit(0);错误处理3详细设计3.1数据存储构造设计元素类型、结点类型typedefstructinttop;栈B¾指针doublearrayN;/用数组来存储NumStack;数字栈typedefstructinttop;chararrayN;(OPStaCk;操作符栈3.2主函数和其他函数的设计与实现voidmain()NumStacknumstackQpStackopstack;charsN;inti=0;numstack.top=0;opstack.top=0;Pushp(<fcopstack,);printf(nEnteryourexpressionandenditwithSCanf("%s”,s);for(i=0;(unsigned)i<strlen(s);i+)Process(&numstack,&opstack,si);printf(Theresultis%f,numstack.arraynumstack.top-1);)intCint(charmychar)将数字符(09)转化为整数(0-9)return(mychar-48);)voidPushNum(NumStack*numstack,doublenum)(数字符进栈函数numstack->top+;numstack->arraynumstack->top-1=num;voidPopNum(NumStack*numstack,double*num)(数字符出栈函数*num=numstack->arraynumstack->top-1;numstack->top-;voidPushOp(OpStack*opstack,charop)操作符进栈opstack->top+;opstack->arrayopstack->top-1=op;voidPopOp(OpStack*opstack,char*op)(操作符入栈函数*op=opstack->arrayopstack->top-1;opstack->top-;)doubleCalc(doublea,doubleb,charc)(/*根据c的类型进行加减运算器函数*/doubleresult;switch(c)(case'+':result=a+b;break;case,-,result=a-bibreak;case'*,esult=a*bbreak;case7':result=a/b;break;returnresult;charPriority(chary,charx)*判断操作符日勺优先级分别返回y哦"="或“>"*/charpriority-<,;switch(x)case÷,:case-,rif(y=-(, H y=',)priority='>break;casecaseif(y=( II y=r y=+ y=-)pority=,>,ibreak;case(*:priority=,>'break;casecase)t1if(y='()priority=,=,ibreak;#':if(y='#')priority-='break;default:PriOrity=E;/出错处理returnpriority;3. 3函数功能分析(1)Cint(charmychar)将数字符(09)转化为整数(0-9)。(2) Calc(doublea,doubleb,charC)根据C的)类型进行+、一、*、/运算。(3) Priority(chary,charx)判断运算符优先权功能，该函数判断运算符cl,c2B优先权，详细优先关系参照表2.1。(4) Process(NumStack*numstack,OpStack*opstack,charx)操作数用对应B¾运算符进行运算功能，运算成果直接返回3.4函数间的调用关系InitStackIPushIBIsdigitHPriorityIlCalcPop图3.1函数调用关系4调试与分析4.1 程序调试算术体现式求值程序较为庞大，调试花费时间较多，重要是在if语句和SWitCh语句上出问题，对于波及时循环B操作开始和结束条件设置很关键，掌握debug后此类错误也可以较快并且成功的处理。多位整数和小数点后数的处理是难点，这就规定我们多熟悉某些算法，对其进行举一反三，来到达自己的需求。运行该程序的Ibiaodashi.exe文献,产生如下图所示H¾界面图4.1按照提醒输入一组体现式，输入完毕后，按回车键，打印体现式计算成果。G:课段¾5W源代玛Debugbiaodashi.exe"Entei*you*expressionandenditwithtt：5.4*5÷<8Z<6-4>>ttTheresultis31.000000Pressanykeytocontinue图4.2图4.3图4.44.2 数据分析从上面的测试成果我们可以看出，当输入英文字母或者不规范的数学体现式时，本程序都会汇报出错。不过本程序也有一定的缺陷。例如：计算的小数位数是有限的（只能计算到小数点背面第六位）当小数点背面超过六位时，计算机会自动省略超过的部分，在初始化空栈时限定了栈B最大容量，当然也可以改善此算法，可以让它计算无穷多位的小数。首先为栈分派以个基本容量，然后在应用过程中，当栈的空间不够使用时再逐渐扩大。设定两个常量：StaCk_init.size（存储空间初始分派量）stackincrement（存储空间分派增量），就可以计算含多位小数的体现式的值。不过由于时间关系，改善算法留给课后完毕。5顾客手册5.1 运行环境本程序开发环境为VC6.0,运行环境为WineIoWS7操作系统，执行文献为：biaodashi.exe5.2 执行文献biaodashi.exe6参照文献1严蔚敏，吴伟民.数据构造（C语言版）.北京：清华大学出版社，2023.2谭浩强.C程序设计.北京：清华大学出版社，2023.3丁峻岭.C语言程序设计.北京：中国铁道出版社，2023.7心得体会这次课程设计让我愈加理解大一学到HC+和这个学期学到的J数据构造（C语言）。课设题目规定不仅规定对书本知识有较深刻B理解，同步规定程序设计者有较强日勺思维和动手能力和愈加理解编程思想和编程技巧。这次课程设计让我有一种深刻的体会，那就是细节决定成败，编程最需要日勺是严谨,怎样的严谨都不过度，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上，因此说细节很重要。程序设计时，也不要怕碰到错误，在实际操作过程中犯的I某些错误还会故意外B收获，感觉课程设计很故意思。在详细操作中这学期所学B数据构造日勺理论知识得到巩固，到达课程设计B¾基本目B¾,也发现自己的局限性之处，在后来的上机中应愈加注意,同步体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机日勺重要作用，尤其算术体现式有了深刻的理解。这个程序是我们3个人完毕H,同步我认为我们0工作是一种团体H工作，团体需要个人，个人也离不开团体，必须发扬团结协作的精神。某个人的离群都也许导致整项工作B失败。实习中只有一种人懂得原理是远远不够日勺，必须让每个人都懂得，否则一种人的错误，就有也许导致整个工作失败。团结协作是我们成功的一项非常重要的保证。而这次课程设计也恰好锻炼我们这一点，这也是非常宝贵的。8小组组员任务分派及工作进度安排表8.1工作进度安排周次任务第16周确定题目，查找资料和设计算法第17周源代码B书写和上机调试第18周写课程设计汇报表8.2小组组员任务分派姓名工作内容源代码的书写和课程设计汇报草稿算法的书写和上机调试课程设计的排版