表达式求值课程设计报告.docx

目录1 需求分析11.1问题描述…………………………………………………………………………………………..11.2基本要求12 概要设计12.1 数据结构12.2各模块间的调用关系及算法设计22.2.1 栈的抽象数据类型的定义……………………………………………………………………....32.2.2栈的基本功能…………………………………………………………………………………….43 详细设计63.1数据存储结构设计63.2 主函数和其它函数的设计与实现63.3函数功能分析83.4 函数间的调用关系94 调试与分析94.1 程序调试94.2 数据分析95 用户手册135.1 运行环境135.2 执行文件136参考文献137心得体会138小组成员任务分配及工作进度安排141 需求分析1.1问题描述在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。本算法的时间复杂度与输入的表达式的长度有密切的关系，在此不作深入分析。1.2基本要求设计友好的用户界面，利用所学工具开发一个简单的表达式求值应用程序，该程序能够对表达式进行加、减、乘、除运算，表达式中的操作数要求在实数范围内；对于异常表达式应能给出错误提示。针对前面的要求分别设计合理的测试数据，比如3.154*(12+18)-23的结果应该是71.62等。概要设计2.1 数据结构表达式求值是程序设计语言编译中的一个最基本的问题。它的实现是栈应用的一个典型例子。本程序使用通常使用的算法为“算符优先法”。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对求值首先要能够正确解释表达式。例如，要对下面的算术表达式求值：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）、组成的，我们称它们为单词。一般地操作数即可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关心运算数和逻辑运算符三类；基本界限符有左右括号和表达式结束等。这里我们仅讨论算数表达式的求值问题。这种表达式只含有加、减、乘、除四种运算符。我们把运算符和界限符统称为算符，他们构成的集合命名为OP。根据上述三条运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一；θ1θ2 θ1的优先权低于θ2θ1=θ2 θ1的优先权等于θ2θ1θ2θ1的优先权高于θ2表2.1定义了算符之间的优先关。表2.1 算符间的优先关系θ1θ2 + - * /（） #+-*/（=）#=2.2 各模块间的调用关系及算法设计各模块间的调用关系如下图：图 2.1 模块间的调用关系为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是:首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的的栈顶元素和当前读入的字符均为“#”）。2.2.1 栈的抽象数据类型的定义ADT Stack{数据对象：D={ai |ai∈ElemSet,i=1,2,…，n, n≧0}数据对象：R1={ai-1,ai|ai-1,ai∈D ,i=2,…，n}约定端为栈顶，ai端为栈底。 InitStack(S)操作结果：构造一个空栈S。Push(S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。 Pop(S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。Priority (c1, c2) 初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Process(a,op,b)初始条件：a,b为实数，op为运算符。操作结果：a与b进行运算，op为算符，返回其值。}ADT S