表达式求值设计报告深入探索计算模型和方法.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;