资源描述：
《数据结构课程设计--表达式求值问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、课程设计(论文)题目名称表达式求值问题课程名称数据结构课程设计学生姓名XXX学号xxxxxxxxx系、专业信息工程系、信息工程类指导教师xxxxxx2010年1月3日13目录1问题描述22需求分析23概要设计23．1抽象数据类型定义23．2模块划分34详细设计44．1数据类型的定义44．2主要模块的算法描述45测试分析75．1程序运行结果75．2程序调试与体会.........................................................................86课程设计总结8参考文献8附录（源程序清单）9
2、131问题描述编写一个表达式求值程序，使输入一个四则运算表达式后，能够返回正确的结果。该表达式由数字0～9、+、-、*、/、括号组成，且表达式必须正确无误。程序的编写可用到栈或队列的基本算法，求出该表达式的值，并分析算法的时间复杂度和运算的结果。2需求分析（1）为实现算符优先算法,可以使用两个工作栈。一个称做OPTR，用以寄存运算符;另一个称做OPND;用以寄存操作数或运算结果。算法的基本思想是：①首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素;②依次读入表达式中每个字符,若是操作数则OPND栈,若是运算符,则和OPTR栈的栈顶运算符比
3、较优先权后做相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为"#")。（2）该程序实现表达式的求值问题：从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则混合运算的求值，输出正确的结果。3概要设计3．1抽象数据类型定义设定栈抽象数据类型的定义采用两个栈的入栈与出栈的操作来进行“运算符和操作数的配对”。程序中主要用到以下抽象数据类型：1）ADTStack{数据对象：D＝{ai
4、ai∈ElemSet,i=2,...,n,n≥0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}约定an
6、端为栈顶，a1端为栈底。基本操作：（1）InitStack(&S)操作结果：构造一个空栈S。13（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返回其值。}ADTStack3．2模块划分本程序包括三个模块：（1）主函数模块void
7、main(){输入表达式；根据要求进行转换并求值；输出结果；}（2）表达式求值模块-----实现具体求值（3）表达式转换模块-----实现转换。三模块之间简单调用关系：主函数模块表达式求值模块模块表达式转换图3.2模块调用图134详细设计4．1数据类型的定义（1）栈类型#defineMAXSIZE100typedefintelmtype;structsqstack{elmtypestack[MAXSIZE];inttop;};（2）运算符号类型charch[7]={'+','-','*','/','(',')','#'};（3）运算符号优先级类型in
8、tf1[7]={3,3,5,5,1,6,0};/*栈内元素优先级*/intf2[7]={2,2,4,4,6,1,0};/*栈外元素优先级*/4．2主要模块的算法描述该程序主要由主函数模块、表达式求值模块、表达式转换模块三个个部分组成。（1）主函数及表达式求值模块voidmain(){intresult;result=EvaluateExpression();/*对EvaluateExpression()进行调用*/}（2）表达式求值模块主函数只调用了EvaluateExpression()函数;而其他的函数则由EvaluateExpression()
9、调用了，因此使得主函数十分简洁明了。其中求值函数流程图如下：13YYYYNNNNNY定义charcC!='#'isdigit(c)SUM=0KERROR!isdigit(c)判断!jsum=sum*10-(c-'0')sum=sum*10+(c-'0')C=GetChar()Push(&OPND,sum)Return(Gettop(OPND))结束图4.2表达式求值模块流程图13（3）表达式转换模块voidtrans(char*exp,char*postexp){在本函数中先初始化一个OP栈，依次读入表达式中的每个字符，若是运算符就进OP栈，若运算符
10、则与OP栈进行比较，直至整个表达式转换完毕。}floatcompvalue(char*postexp){st
