表达式求值课程设计报告.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 函数间的调用关系9 4 调试与分析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 概要设计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之间的优先关系至多是下面三种关系之一； 12 1的优先权高于2 表2.1定义了算符之间的优先关。表2.1 算符间的优先关系12 + - * / （ ） #+-*/（#=2.2 各模块间的调用关系及算法设计 各模块间的调用关系如下图：主程序模块初始化两个栈输入表达式表达式计算输出结果图 2.1 模块间的调用关系为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是:(1) 首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；(2) 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的的栈顶元素和当前读入的字符均为“#”）。2.2.1 栈的抽象数据类型的定义ADT Stack数据对象：D=ai |aiElemSet,i=1,2,，n, n0数据对象：R1=|ai-1,aiD ,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 Stack2.2.2栈的基本功能InitNumStack(NumStack *s) 和InitOpStack(OpStack *s)分别构造操作数栈与构造算符栈， PushNum(NumStack *numstack,double num)操作数栈插入num为新的栈顶元素，PushOp(OpStack *opstack,char op) 算符栈插入op为新的栈顶元素，PopOp(OpStack *opstack,char *op) 删除运算符栈s的栈顶元素，用p返回其值，PopNum(NumStack *numstack,double *num)删除操作数栈s的栈顶元素，用p返回其值。其中部分操作的算法如下：void Process(NumStack *numstack,OpStack *opstack,char x)/根据输入的表达式求值，若表达式输入正确则返回结果，否则返回错误处理 double a,b;char c; static double tempnum=0.00000000;static int len=10;static int dot=0,flags=0; if(isdigit(x) | x=.)/判断输入的字符是否是09或小数点 /*这段是处理数字符*/ if(x=.)dot=1; else if(dot=0) tempnum=tempnum*10+Cint(x);/Cint将字符数转化为整数 else tempnum=tempnum+(double)Cint(x)/len; len*=10; else /*这段是处理操作符*/ if(flags=0 & x!=() PushNum(numstack,tempnum);tempnum=0.00000000;len=10;dot=0; switch(Priority(opstack-arrayopstack-top-1,x) /*根据Priority的返回值做相应的处理*/ case :PushOp(opstack,x);flags=0;break;/大于进栈 case :/小于出栈进行运算并把结果入栈 PopOp(opstack,&c); PopNum(numstack,&b); PopNum(numstack,&a); PushNum(numstack,Calc(a,b,c);flags=1; Process(numstack,opstack,x);break; case =:PopOp(opstack,&c);flags=1;break;/脱括号处理 default:printf(Wrong Express!);exit(0);/错误处理 3 详细设计3.1数据存储结构设计元素类型、结点类型typedef struct int top;/栈的指针 double arrayN;/用数组来存储NumStack;/数字栈typedef struct int top; char arrayN;OpStack;/操作符栈3.2 主函数和其它函数的设计与实现void main() NumStack numstack;OpStack opstack;char sN;int i=0; numstack.top=0;opstack.top=0; PushOp(&opstack,#); printf(nEnter your expression and end it with #:);scanf(%s,s); for(i=0;(unsigned)i top+; numstack-arraynumstack-top-1=num;void PopNum(NumStack *numstack,double *num)/数字符出栈函数 *num=numstack-arraynumstack-top-1; numstack-top-;void PushOp(OpStack *opstack,char op)/操作符进栈 opstack-top+; opstack-arrayopstack-top-1=op;void PopOp(OpStack *opstack,char *op)/操作符入栈函数 *op=opstack-arrayopstack-top-1; opstack-top-;double Calc(double a,double b,char c)/*根据c的类型进行加减运算器函数*/ double result; switch(c) case +:result=a+b;break; case -:result=a-b;break; case *:result=a*b;break; case /:result=a/b;break; return result;char Priority(char y,char x)/*判断操作符的优先级分别返回*/ char priority=;break; case *: case /:if(y=( | y=#| y=+ | y=-)priority=;break; case (:priority=;break; case ):if(y=()priority=;break; case #:if(y=#)priority=;break; default:priority=E;/出错处理 return priority;3.3函数功能分析 （1）Cint(char mychar) 将数字符(09）转化为整数(0-9)。 (2) Calc(double a,double b,char c)根据c的类型进行+、*、/运算。 (3)Priority (char y,char x) 判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表2.1。 (4)Process (NumStack *numstack,OpStack *opstack,char x )操作数用对应的运算符进行运算功能，运算结果直接返回3.4 函数间的调用关系图3.1 函数调用关系4 调试与分析4.1 程序调试算术表达式求值程序较为庞大，调试花费时间较多，主要是在if语句和switch语句上出问题，对于涉及的循环的操作开始和结束条件设置很关键，掌握debug后此类错误也能够较快而且成功的解决。多位整数和小数点后数的处理是难点，这就要求我们多熟悉一些算法，对其进行举一反三，来达到自己的需求。运行该程序的biaodashi.exe文件,产生如下图所示的界面 图 4.1按照提示输入一组表达式, 输入完成后，按回车键, 打印表达式计算结果。 图 4.2 图 4.3 图 4.44.2 数据分析从上面的测试结果我们可以看出，当输入英文字母或者不规范的数学表达式时，本程序都会报告出错。但是本程序也有一定的缺点。例如：计算的小数位数是有限的（只能计算到小数点后面第六位）当小数点后面超过六位时，计算机会自动省略超出的部分，在初始化空栈时限定了栈的最大容量，当然也可以改进此算法，可以让它计算无穷多位的小数。首先为栈分配以个基本容量，然后在应用过程中，当栈的空间不够使用时再逐渐扩大。设定两个常量：stack_init_size(存储空间初始分配量)stackincrement(存储空间分配增量)，就能够计算含多位小数的表达式的值。但是由于时间关系，改进算法留给课后完成。5 用户手册5.1 运行环境本程序开发环境为VC 6.0，运行环境为windows7操作系统，执行文件为：biaodashi.exe5.2 执行文件6 参考文献 1严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2007. 2谭浩强.C程序设计.北京：清华大学出版社，2005.3丁峻岭.C语言程序设计.北京：中国铁道出版社，2003.7 心得体会这次课程设计让我更加了解大一学到的C+和这个学期学到的数据结构（C语言）。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上，所以说细节很重要。 程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之处，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。 这个程序是我们3个人完成的，同时我认为