数据结构课程设计报告正文.doc

课程设计(论文)题目名称表达式求值问题课程名称数据结构课程设计学生姓名陈春林学号0841330197系、专业信息工程系、.........................................................................86课程设计总结8参考文献8附录(源程序清单)91问题描述编写一个表达式求值程序,使输入一个四则运算表达式后,能够返回正确的结果。该表达式由数字0~9、+、-、*、/、括号组成,且表达式必须正确无误。程序的编写可用到栈或队列的基本算法,求出该表达式的值,并分析算法的时间复杂度和运算的结果。2需求分析(1)为实现算符优先算法,可以使用两个工作栈。一个称做OPTR,用以寄存运算符;另一个称做OPND;用以寄存操作数或运算结果。算法的基本思想是:①首先置操作数栈为空栈,表达式起始符“#”为运算符栈的栈底元素;②依次读入表达式中每个字符,若是操作数则OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后做相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为"#")。(2)该程序实现表达式的求值问题:从键盘读入一个合法的算术表达式,利用算符优先关系,实现对算术四则混合运算的求值,输出正确的结果。“运算符和操作数的配对”。程序中主要用到以下抽象数据类型:1)ADTStack{数据对象:D={ai|ai∈ElemSet,i=2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:(1)InitStack(&S)操作结果:构造一个空栈S。(2)GetTop(S,&e)初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。(3)Push(&S,e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。(4)StackEmpty(&s)初始条件:栈S已存在。操作结果:若S为空栈,则返回TRUE,否则返回FALSE(5)Pop(&S,&e)初始条件:栈S已存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。}:(1)主函数模块voidmain(){输入表达式;根据要求进行转换并求值;输出结果;}(2)表达式求值模块-----实现具体求值(3)表达式转换模块-----实现转换。三模块之间简单调用关系:(1)栈类型#defineMAXSIZE100typedefintelmtype;structsqstack{elmtypestack[MAXSIZE];inttop;};(2)运算符号类型charch[7]={'+','-','*','/','(',')','#'};(3)运算符号优先级类型intf1[7]={3,3,5,5,1,6,0};/*栈内元素优先级*/intf2[7]={2,2,4,4,6,1,0};/*栈外元素优先级*/、表达式求值模块、表达式转换模块三个个部分组成。(1)主函数及表达式求值模块voidmain(){intresult;result=EvaluateExpression();/*对EvaluateExpression()进行调用*/}(2)表达式求值模块主函数只调用了EvaluateExpression()函数;而其他的函数则由EvaluateExpression()调用了,因此使得主函数十分简洁明了。其中求值函数流程图如下:!='#'isdigit(c)SUM=0KERROR!isdigit(c)判断!jsum=sum*10-(c-'0')sum=sum*10+(c-'0')C=GetChar()Push(&OPND,sum)Return(Gettop(OPND))(3)表达式转换模块voidtrans(char*exp,char*postexp){在本函数中先初始化一个OP栈,依次读入表达式中的每个字符,若是运算符就进OP栈,若运算符则与OP栈进行比较,直至整个表达式转换完毕。}pvalue(char*postexp){struct{floatdata[MaxSize];inttop;}st;5测试分析5