数据结构课程设计报告表达式求值演示

《数据结构课程设计报告表达式求值演示》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件学院课程设计报告书课程名称数据结构设计题目算术表达式求值演示程序专业班级嵌入式软件10-1班学号1020030104姓名董俊指导教师冯永安2012年1月18目录1.设计时间22.设计目的23.设计任务24.设计内容24.1需求分析24.2总体设计24.2.1抽象数据类型的定义24.2.2函数模块说明34.2.3主函数流程图44.2.4函数模块调用关系54.2.5运算符间的优先关系54.3详细设计64.3.1数据类型的定义64.3.2函数调用关系84.3.3主要模块的算法描述84.4测试与分析104.4.1测试10184.4.2分析114.5附录115.总结与心得体会16

2、参考文献17成绩评定17181设计时间2012.1.4-2012.1.62设计目的掌握栈的使用和把一个表达式翻译成能够正确求值的一个机器指令序列的原理。3设计任务设计一个程序，演示用算符优先法对算术表达式求值的过程。4设计内容4.1需求分析1、程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是还语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。2、输入的形式和输入值的范围：以字符串的形式输入表达式，以“#”结束。3、输出的形式：在计算过程中遇到的

3、问题或最终的答案将显示在屏幕上，同时所计算的表达式的最终的结果也将保存在文件中。4、测试数据：输入“3*(7-2)#”时，输出“15.000000”，测试正确；输入“!(9-2)#”时，输出“输入错误！”，测试正确。4.2总体设计4.2.1抽象数据类型定义ADTStack{数据对象：D={

4、∈ElemSet,i=1,2,…，n,n≧0}数据对象：R1={<>

5、,,i=2,…，n}约定端为栈顶，端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。18GetTop(S)初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push(&S，ch)初始条件：栈S

6、已存在。操作结果：插入元素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()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack4.2.2函数模块说明为实现算符优先算法，可以使用两个

7、工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是：(1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素(2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR18栈的栈顶元素和当前读入的字符均为“#”）。算法中还调用了两个函数。其中Precede是判定运算符栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；Operateo为进行二元运算aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中

8、间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。4.2.3主函数流程图184.2.4函数模块调用关系4.2.5运算符间的优先关系θ1θ2+-*/()#+>>><<>>->>><<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=184.3详细设计4.3.1数据类型的定义及基本操作//=====ADTStack的表示与实现=====//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZT100;#defineSTACKINCREMENT10typedefstruct{SElemType*base;SEl

9、emType*top;intstacksize;}SqStack;//-----基本操作的算法描述-----StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusGetTop(SqStackS,SElemType&e){if(S.t