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

数据结构课程设计报告（2012）数据结构课程设计报告题 目： 栈的应用：表达式求值 院 （系）： 信息科学与工程学院 专业班级： 软件工程1102班 学生姓名： 学 号： 指导教师： 20 13 年 6 月 8 日至20 13 年 6 月 21 日目 录目 录21 概 述1 1.1 课程设计目的11.2 课程设计内容1 2 系统需求分析1 2.1 系统目标1 2.2 主体功能12.3 开发环境1 3 系统概要设计23.1 系统的功能模块划分23.2 系统流程图2 4系统详细设计3 5 测试6 5.1 测试方案65.2 测试结果6 6 小结8参考文献10附录1 源程序清单113表达式求值1 概 述 1.1 课程设计目的1要求学生达到熟练掌握C语言的基本知识和技能。2了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。3提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。4培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。5初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。1.2 课程设计内容设计一个表达式求值的程序。该程序必须可以接受包含（，），+，-，*，/，%，和（求幂运算符，ab=ab）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。2 系统需求分析2.1 系统目标利用栈设计一个程序，该程序能够用于表达式求值，程序将读入的中缀表达式转换为后缀表达式，然后读取后缀表达式，输出结果。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值（精确到小数点后两位），也可能是错误信息“ERROR IN INFIX NOTATION”。2.2 主体功能能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是否语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。2.3 开发环境Microsoft Visual C+ 6.03 系统概要设计3.1 系统的功能模块划分1.判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回1，不是就返回0。2.求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，在根据数字的大小判断优先级。+，-优先级相同，返回数字相同 ，*，/也是。3.表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。4.主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋值到浮点型的result，输出result。5.两个栈的函数设计： 栈的初始化函数charInit_SeqStack() Init_SeqStack() 栈判空 Empty_SeqStack() char Empty_SeqStack() 入栈函数 Push_SeqStack() charPush_SeqStack() 出栈函数 Pop_SeqStack() charPop_SeqStack() 取栈顶函数 GetTop_SeqStack() charGetTop_SeqStack() 销毁栈 Destory_SeqStack() charDestory_SeqStack()3.2 系统流程图 开始优先级比较算法Operate 算法建立栈存放操作字符存放数据计算结束表达式式否合法输出表达式值输出错误提示图1 系统流程图4系统详细设计1. 基本分析:在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式求值程序的最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。 2. 中缀表达式求值: 中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“”，如：(7+15)*(23-28/4)。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即： (1) 从左到右； (2) 先乘除，后加减； (3) 先括号内，后括号外。 运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一： 12，1的优先权高于2。 实现算符优先算法时需要使用两个工作栈：一个称作operator，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。算法的基本过程如下：首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“”压入运算符栈； 依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理： (1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入operand栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求解结束。 int ExpEvaluation() /*读入一个简单算术表达式并计算其值。*/ InitStack(&operand); InitStack(&operator); PushStack(&operator, ); printf(nn Please input an expression (Ending with ) :);ch=getchar(); /*读入表达式中的一个字符*/ while(ch!=|GetTop(operator)!=) if(!In(ch, OPS) /*判断ch是否运算符*/ a=GetNumber(&ch); /* 用ch逐个读入操作数的各位数码，并转化为十进制数a */ PushStack(&operand,a); else switch(Compare(GetTop(operator),ch) case : PopStack(&operator, &op); PopStack(&operand, &b); PopStack(&operand, &a); v=Execute(a,op,b); PushStack(&operand,v); break; v=GetTop(operand); return(v); 为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达式“（a+b*c）-d/e”的后缀表达式为：“abc*+de/-”。3. 后缀表达式求值: 计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。 下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以#为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换问题。 double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/ SeqStarck s; ch=*A+ ; InitStack(s); while(ch!= # ) if(ch!=运算符) PushStack(s, ch); else PopStack(s, &a); PopStack(s, &b); /*取出两个运算量*/ switch(ch) case ch=+： c=a+b; break ; case ch=-： c=a-b; break ; case ch=*： c=a*b; break ; case ch=/ ： c=a/b; break ; case ch=%：c=a%b; break ; PushStack (s, c) ; ch=*A+ ; PopStack(s, result) ;return result ; 4. 中缀表达式转换成后缀表达式 :将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。读者不难写出算法，在此不再赘述。程序的整体算法分两步： 第一步，从”input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果存放在一个temp文件中。第二步，从temp文件中读取中缀表达式，并应用操作栈Operands计算后缀表达式结果，将结果输出到”output.txt”文件中。5 测试5.1 测试方案设计针对程序的input.txt文件，并将运行结果与期望测试进行比较。5.2 测试结果 图 1 图 22基本测试：在input文件中输入表达式如下图2 则输出结果如下图3 图2 图32. 扩展测试：在input文件中输入表达式如下图5： 则输出结果如下图6： 图5 图63容错测试：在input文件中输入表达式如下图7： 则输出结果如下图8： 图7 图86 小结通过此次的课程设计，巩固和加深了我对栈、队列、字符串等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（；提高利用计算机分析解决综合性实际问题的基本能力。在细节问题的分析上，较以往有了很大的提高。在寻求最优解的问题上，也能够找到多种解决方案来使自己的程序收放自如。如，在处理实数的问题上，我采用的是每取得一个字符，就立刻对此字符进行处理的方法。其实，我们可以用一个字符数组，来存储连接着的一系列数字字符，然后再通过atof函数，直接得到字符数组中所存储的数字。再如，对负数问题的处理上，我最初的想法是通过一个标志mark来记录前面的字符是否是负号（或减号），再在后面取到除符号外的数字时，选择是否添加负号。另外，与其他人不同的是，在我的课程设计中，Compare（）函数与其他有着很大的区别。通常情况下，同学们参照课本，都会采用占用7*7=49个空间的数组来分别存储对应两个字符的优先级符号，并对两个字符进行预算之后得到数组中的位置。虽然7*7的数组所占的空间并不是非常大，但在我看来这也是一种浪费，并且空间的浪费并没有换回时间一定的节省。因此，我采用了一种常规的思路。将各种运算符按照数学逻辑上的优先顺序进行排序，并得到两个字符之间的优先级关系。这样一来，我们将不再需要那7*7的数组，且时间复杂度并不大幅增涨。在这个课程设计中，运用到的数据结构的知识主要是栈的知识。栈在各种软件系统中，应用非常广泛。栈的的存储特性(LIFO先进后出)，使得在用栈来编程时，思路清晰明了。在使用递归算法时，栈也是一种很好的选择。此外，这次的课程设计进一步加强了我们运用C语言进行编程，调试，处理问题的能力，加深了我们对算法及数据结构的认识。同时我也意识到，开发程序的早期计划要做的充分，以免出现程序完成后发现不足而带来的修改麻烦。虽然这只是一个小小的软件，但对我们之后的影响确实很大的。29参考文献1范策，周世平，胡哓琨.算法与数据结构（C语言版）M. 北京：机械工业出版社，20042 严蔚敏.数据结构（C语言版）. 北京：清华大学出版社，20043 许卓群，杨冬青，唐世渭，张铭. 数据结构与算法. 北京：高等教育出版 社，20044 徐孝凯. 数据结构实用教程（第二版）. 北京：清华大学出版社，20065 何钦铭等编著数据结构课程设计杭州：浙江大学出版社，2007 2耿国华等编著数据结构用C语言描述北京：高等教育出版社20113徐健等编著数据结构上机指导与习题解析南京：南京大学出版社，20074陈建新等编著数据结构实验指导与课程设计教程北京：科学出版社，2010附 录附录1 源程序清单#include #include #include int PrintError = 0; /*全局变量，0代表正常，1代表表达式出错*/typedef struct Node *PtrToNode; /*栈的定义*/typedef PtrToNode Stack;typedef struct FNode *Ptr_Fn;typedef Ptr_Fn FStack;typedef struct FNodefloat Element;Ptr_Fn Next;typedef struct Nodechar Element;PtrToNode Next;/* 函数声明*/int FisEmpty(FStack S);void FPush(float X,FStack S);float FTop(FStack S);void FPop(FStack S);int IsEmpty(Stack S);void MakeEmpty(Stack S);void Push(char X,Stack S);char Top(Stack S);void Pop(Stack S);void ConvertToPost(FILE *In, Stack Whereat,FILE *Temp);void Reverse(Stack Rev);void Calculate(FILE *Change, Stack Whereat,FILE *Temp);void cover(); void mainmenu();void printoutput();void author();/* 主函数*/void main() cover(); mainmenu(); /* 封面函数*/void cover() system(color f0); printf(nnn);printf(ttt数据结构课程设计 之n);printf(ttt 表达式求值n);printf(nnnnnn);printf(ttt made by 薛国庆nn);printf(ttt 软件工程1102nn);printf(ttt 2013年6月nnnn);printf(ttttttt 按Enter继续);getch();/* 关于作者*/void author()int c;system(cls);printf(nn);printf(t关于作者nn);printf(ttt 程序员: nn);printf(ttt 测试员: nn);printf(ttt 文档员: nn);printf(nnnn); printf(tt _ n); printf(tt | 0 返回主菜单 |n); printf(tt | 1 退出 |n);printf(tt |_|n); printf(ttt 请选择操作(0-1):); scanf(%d,&c); switch(c) case 0: mainmenu();break; case 1: exit(0); default:mainmenu();/*操作目的：将用户输入的Input.txt文件中的中缀表达式计算结果存如Output.txt文件中。初始条件：用户将中缀表达式，逐行输入到Input.txt文件中。操作结果：自动生成一个Output.txt文档将结果逐行输出。*/int save() int c;FILE *InputFile, *OutputFile,*Temp; /*Temp用来存放后缀表达式*/Stack Whereat; /*记录后缀表达式中操作数与运算符的顺序*/char sample; /*用来存放*/InputFile = fopen(Input.txt,r);OutputFile = fopen(Output.txt,w);Whereat = malloc(sizeof(struct Node);Whereat-Next = NULL;if (!InputFile | !OutputFile) printf(intput or output file(s) do not exist.n);return(1);sample = getc(InputFile); while ( sample != EOF) /*EOF为文件结束的标志*/Temp = fopen(Temp.txt,w+);ungetc(sample,InputFile); /* 将sample字符退回至输入流中*/ConvertToPost(InputFile,Whereat,Temp);/*中缀后缀*/if (PrintError) fprintf(OutputFile,Error); fscanf(InputFile,n,&sample); PrintError = 0; else if (IsEmpty(Whereat) = 1) /*跳过在input文件中的空格*/else if (IsEmpty(Whereat) != 1) Reverse(Whereat); /*将Whereat栈倒置*/if (Top(Whereat) = B) /*B表示运算符*/PrintError = 1; /*后缀表达式第一个元素是运算符号则表达式错误*/fclose(Temp);Temp = fopen(Temp.txt,r+);Calculate(OutputFile, Whereat,Temp);/*计算后缀表达式的结果*/fclose(Temp);MakeEmpty(Whereat); /* 将Whereat栈置空*/putc(n,OutputFile);/* 在输出文件中换行*/sample = getc(InputFile); free(Whereat); fclose(InputFile);fclose(OutputFile);remove(Temp.txt); /*释放空间*/system(cls); printf(nnnnttt恭喜!Output.txt文件已经生成!n);printf(nnnn); printf(tt _表达式求值_ nn); printf(tt | 0 返回主菜单 |nn); printf(tt | 1 退出 |nn);printf(tt |_|n); printf(ttt 请选择操作(0-1):); scanf(%d,&c); switch(c) case 0: mainmenu();break; case 1: exit(0); default:mainmenu();return 1;/*操作目的：将自动生成的Output.txt中每一行的结果读取输出。初始条件： 生成一个Output.txt文档将结果逐行输出。操作结果：在窗口逐行输出结果*/* Output输出函数*/void printOutput() int c; int i=0;char str100100; /*二维数组用来存放字符串*/char a100; /*中间变量*/FILE *fp;system(cls);fp=fopen(Output.txt,rb);if(fp=NULL)printf(Open File error!);while(!feof(fp)fscanf(fp,%s,a);strcpy(stri+,a); /*将a赋给stri+*/ printf( 欢迎使用nn); printf(ttInput.txt文件中每一行的中缀表达式的计算结果如下:nn);for (i=0;i38;i+) /*可以根据Output.txt中结果的个数改变循环次数*/printf(tt%sn,stri);fclose(fp);printf(nnnn); printf(tt _ n); printf(tt | 0 返回主菜单 |n); printf(tt | 1 退出 |n);printf(tt |_|n); printf(ttt 请选择操作(0-1):); scanf(%d,&c); switch(c) case 0: mainmenu();break; case 1: exit(0); default:mainmenu();/*操作目的：将Input.txt每一行的结果读取输出。初始条件： Input.txt文档存在。操作结果：在窗口逐行输出Input.txt文件中的中缀表达式。*/* Input输出函数*/void printInput() int c; int i=0;char str100100;char a100;FILE *fp;system(cls);fp=fopen(Input.txt,r);if(fp=NULL)printf(Open File error!);while(!feof(fp)fscanf(fp,%s,a);strcpy(stri+,a); printf( 欢迎使用nn); printf(ttInput.txt文件中每一行的中缀表达式如下:nn);for (i=0;iNext=NULL);int FIsEmpty(FStack S)return(S-Next=NULL);/* 两种类型的弹出栈顶元素*/*弹出堆栈栈顶元素*/void Pop(Stack S)PtrToNode FirstCell;if (IsEmpty(S)printf(栈为空);elseFirstCell = S-Next;S-Next = S-Next-Next;free(FirstCell);/*弹出float栈顶元素*/void FPop(FStack S)Ptr_Fn FirstCell;if (FIsEmpty(S)printf(栈为空);elseFirstCell = S-Next;S-Next = S-Next-Next;free(FirstCell);/* 两种类型的置空栈*/*将堆栈置空*/void MakeEmpty(Stack S)if (S = NULL)printf(你必须先建立一个栈!);elsewhile (!IsEmpty(S)Pop(S);/*将float堆栈置空*/void FMakeEmpty(FStack S)if (S = NULL)printf(你必须先建立一个栈!);elsewhile (!IsEmpty(S)Pop(S);/* 两种类型的元素进栈*/*元素进栈*/void Push(char X, Stack S)PtrToNode TmpCell;TmpCell = (PtrToNode)malloc(sizeof(struct Node);if (TmpCell = NULL)printf(空间不够!);elseTmpCell-Element = X;TmpCell-Next = S-Next;S-Next = TmpCell;/*