基于c语言的表达式求解课程设计.doc

*实践教学* 兰州理工大学软件学院2012年春季学期 算法与数据结构 课程设计题 目： 专业班级： 姓 名： 学 号： 指导教师： 成 绩：_ _29目 录摘 要3前 言4正 文51、采用类c语言定义相关的数据类型52、各模块的伪码算法83函数的调用关系104算法模块的关系调用105、调试分析126、测试结果147、软件使用说明书15设 计 总 结16致 谢17参考文献18附录1 源程序19摘 要用一个一维数组存放从键盘输入的表达式,表达式中可包含：加（+）、减（-）、乘（*）、除（/）,括号（,）等运算符。要对输入的表达式进行检查，看是否是合格的表达式，如遇到错误则终止，不进行计算；例如：括号不配对、除数不为零等；输入的表达式可以是常量表达式，也可以是变量表达式；如果是常量表达式，则直接输出结果；如果是变量表达式，通过对变量的不断赋值，计算变量取不同值时表达式的结果。参与运算的操作数可以是整型，也可以是浮点型。程序执行的的命令：（1）、输入表达式 （2）、计算表达式（3）、输出结果 （4）、退出系统关键词： 数据结构；表达式求值；栈前 言栈是一种数据结构，它按照后进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈应用的又一个典型例子。正 文1、采用类c语言定义相关的数据类型设定栈的数据类型定义ADT Stack数据对象： D=ai| aiDateType,i=1,2,，n，n=0数据关系： R1=| ai-1,aiD,i=2,n基本操作：InitStack(& S)操作结果：构造一个空栈S；StackEmpty(S)初始条件：栈S已存在；操作结果：若S为空栈，则返回0，否则返回1；GetTop(S,&e)初始条件：栈S已存在；操作结果：若栈S不空，则以e返回栈顶元素；Push(&S,e)初始条件：栈S已存在；操作结果：在栈S的栈顶插入新的栈顶元素e；Pop(&S,&e)初始条件：栈S存在；操作结果：删除S的栈顶元素，并以e返回其值；设定表达式求值的抽象数据类型定义： class Evapublic: void Getcha(char *name); 操作结果：重键盘获取表达式 OperandType EvaluateExpression();操作结果：计算表达式的值 void Output();操作结果：输出常量表达式的结果 char Menu(); 操作结果：主菜单选项 int check();操作结果：检查表达式是否正确，若正确返回1，否则返回0； int Simple(char *p, int i);操作结果：判断运算符-，若是减号返回1，否则返回0； OperandType Evaluate();操作结果：对变量表达式中的变量进行提取；存放在word10中； double change();操作结果：对变量表达式中的变量赋值； char Menu2();操作结果：对变量表达式中变量赋值的菜单； void Put();操作结果：输出变量表达式的结果； void Help();操作结果：调用一个.txt文档，为用户提供使用帮助；private: char cha100; /存放输入的表达式 char word10; /存放表达式中的变量 int swit(char op);操作结果：判断运算符在优先级表中的下标； int In(char c);操作结果：判断是否是运算符，若是返回1，否则返回0； char Precede(char op, char c);操作结果：比较两个字符的优先级，返回、或=； OperandType Operate(OperandType a, char op, OperandType b);操作结果：计算两个操作数的运算，返回运算的结各模块的伪码算法 栈类型 思想： 本程序中栈采用的链式存储结构，因为存放操作符和操作数的结点类型不一样，所以设计了两个结点。栈的基本操作采用了重载的方法，使两种结点类型都能使用。 （1）、存放操作符的结点： struct node2 char data2; /存放操作符 node2 *next2; （2）、存放操作数的结点：struct node double data; /存放操作数 node *next;栈的基本操作设置如下：int InitStack(Linked_stack *top)/初始化，设栈为空栈（top-next=NULL）；int StackEmpty(Linked_stack top)/若栈为空（top-next=NULL），则返回1，否则返回0；int Push(Linked_stack top, Datetype e)/若申请动态内存成功，则在top的栈顶插入元素e，并返回1， /否则返回0；int Pop(Linked_stack top, Datetype *e)/若栈不空，则删除top的栈顶元素并以e带回其值，并且返回1，/否则返回0；int GetTop(Linked_stack top, Datetype *e)/若栈top不空，则以e带回其值，且返回1，否则返回02、各模块的伪码算法 思想： 本程序中栈采用的链式存储结构，因为存放操作符和操作数的结点类型不一样，所以设计了两个结点。栈的基本操作采用了重载的方法，使两种结点类型都能使用。 （1）、存放操作符的结点： struct node2 char data2; /存放操作符 node2 *next2; （2）、存放操作数的结点：struct node double data; /存放操作数 node *next;栈的基本操作设置如下：int InitStack(Linked_stack *top)/初始化，设栈为空栈（top-next=NULL）；int StackEmpty(Linked_stack top)/若栈为空（top-next=NULL），则返回1，否则返回0；int Push(Linked_stack top, Datetype e)/若申请动态内存成功，则在top的栈顶插入元素e，并返回1， /否则返回0；int Pop(Linked_stack top, Datetype *e)/若栈不空，则删除top的栈顶元素并以e带回其值，并且返回1，/否则返回0；int GetTop(Linked_stack top, Datetype *e)/若栈top不空，则以e带回其值，且返回1，否则返回3函数的调用关系主程序输入表达式计算表达式输出结果退出程序4算法模块的关系调用开始建立空栈取栈顶元素入栈出栈若s存在并非空，用e返回s的栈顶元素若s已存在插入e为新的栈顶元素若s已存在删除s的栈顶元素输入表达式YesNo计算表达式正确?YesNO，出现错误提示输出结果退出正确？5、调试分析a、 调试中遇到的问题及对问题的解决方法测试项目测试用例计算结果预期结果实验结果基本测试3331+2*3-4/25511+2233331+22*(5-3)/412122.5-3.4/2+1*22.82.822325625622.5350535.250535.2-2*3+4/2-4-43*(-2-4)+2-16-16X2+x x=31212容错测试1+2（2与（之间没有操作符2与（之间没有操作符2/0除数为0除数为03/(2*3-6)+2除数为0除数为02+3)(-5括号不匹配括号不匹配1+1出现3个+出现3个+2 22与2之间无操作符2与2之间无操作符1#1#是非法字符#是非法字符3(2+5)3与（之间没有操作符3与（之间没有操作符b、算法的时间复杂度和空间复杂度时间复杂度和空间复杂度均为O（n）6、测试结果输入错误的表达式运行结果输入正确的表达式运行结果7、软件使用说明书在程序无误运行之后屏幕出现对话窗口提示,在数字提示下进行输入表达式,检查表达式,计算表达式,输出结果.设 计 总 结这次的课程设计让我感受颇多，我就觉得我们的这一个课题应该是一个还不错的题目，因为上课的时候我认真听了，也就是说我应该可以做好，而且像这样的问题在网络上可以找到很多相关的内容。但是在我们真正开始做的时候我却发现问题不是我想像的那么简单，我们遇到了很多的麻烦。 首先，在我们开始做的时候发现根本不知道该从什么地方下手，接着我们便开始上网查找，但是网络上的东西很多都是没有用的，于是自己开始去图书馆找资料，看了很有关哈夫曼方面的知识以后，开始对栈与队列有了一定的了解，于是在掌握了这些基础知识之上，我就对我们的课题进行分析。其次，我们发现我遇到了不少问题，但是当我们遇到不懂的问题，我就和组员一起讨论，逐步将程序的一个个功能实现。虽然设计的过程是比较辛苦的，但是当我们看到设计成功的时候我们非常的开心。毕竟这一设计是我们亲手完成的。毕竟我们从这次的课程设计中学到了很多知识。例如：栈与队列的算法，我们是经过了认真的复习，才基本掌握了。还有，我们还复习了C+的相关知识，因为我们感觉到在编程序的时候，我们明显感觉到自己的C+，以及数据结构方面的知识还是有所欠缺的。例如：我们的课程设计用到了文件有关方面的知识，这些知识都是我们以前比较薄弱的地方，通过此次课程设计我们更加理解了这方面的内容。这次的课程设计不仅考查了我们理论知识，更主要的是考查了我们动手实践的能力，考查了我们用C+，数据结构编程的能力。而且还考查了我们组员分配和协作的能力。在这一周中，我们合理的分配了任务，并经过我们共同的努力才把这一课题基本完成了。从这次的课程设计中，我看到了自己的不足，首先就是比较轻浮，不能够踏踏实实的，其次，就是我个人的动手操作能力，即上机编程能力还是十分欠缺的，这还是我们平时锻炼的少所造成的。所以在以后的学习中我们要加强这方面的锻炼，为我们走上社会打下坚实的基础。所以此次的课程设计对我来说意义重大。致 谢经过这两周的课程设计，我们获得了许多在课堂上听课而不能获得的知识，首先我们要感谢学校给我们安排的这次的算法与数据结构程序设计实习，然后我要感谢老师们对我们热心的指导和帮助，是他教会了我们怎样解决问题的方法，这样我们的软件设计才会更加顺利地进行，并且充分掌握了设计程序的方法。我们还要感谢许多同学的帮助，他们的帮助对于我们来说也是必不可少的。总之，是有了他们的帮助，我们才能顺利地完成软件设计，在这里我们要向他们说一句：谢谢，非常感谢！你们辛苦了！参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社.附录1 源程序#include #include #include #define PLUS 0 #define MINUS 1 #define POWER 2 #define DIVIDE 3 #define LEFTP 4 #define RIGHP 5 #define STARTEND 6 #define DIGIT 7 #define POINT 8 #define NUM 7 #define NO 32767 #define STACKSIZE 20 char a=+,-,*,/,(,),#; int PriorityTable77= 1, 1,-1,-1,-1, 1, 1, 1, 1,-1,-1,-1, 1, 1, 1, 1, 1, 1,-1, 1, 1, 1, 1, 1, 1,-1, 1, 1, -1,-1,-1,-1,-1, 0, NO, 1, 1, 1, 1,NO, 1, 1, -1,-1,-1,-1,-1,NO, 0; int menu(void); void InputExpression(char str) int len; printf(Input expression string:n); scanf(%s,str); len=strlen(str); strlen=#; strlen+1=0; int GetCharType(char ch) int i; for(i=0;i=0 & ch=0 & strpp=0 & strpp=0 & strpp=9) number=number+(strpp-48)/temp; temp=temp*10; pp+; OPNDtopNd=number; topNd+; break; case PLUS: case MINUS: case POWER: case DIVIDE: if(PriorityTableOPTRtopTr-1CharType=-1) OPTRtopTr=CharType; topTr+; pp+; else OPNDtopNd-2=Operate(OPNDtopNd-2,OPTRtopTr-1,OPNDtopNd-1); topNd-; topTr-; break; case LEFTP: OPTRtopTr=CharType; topTr+; pp+; break; case RIGHP: while(OPTRtopTr-1!=LEFTP) if(OPTRtopTr-1=STARTEND)return(0); if(PriorityTableOPTRtopTr-1CharType=1) OPNDtopNd-2=Operate(OPNDtopNd-2,OPTRtopTr-1,OPNDtopNd-1); topNd-; topTr-; else break; topTr-; pp+; break; case STARTEND: while(OPTRtopTr-1!=STARTEND) OPNDtopNd-2=Operate(OPNDtopNd-2,OPTRtopTr-1,OPNDtopNd-1); topNd-; topTr-; if(topNd=1) *Result=OPND0; return(1); else return(0); return(1); void main() int num,flag; double result; char str256; str0=0; while(1) num=menu(); switch(num) case 1: InputExpression(str); flag=0; printf(%sn,str); getchar(); break; case 2: if(str0=0) printf(Expression is Empty!); getchar(); break; if(!EXCUTE(str,&result) printf(The expression has error!n); getchar(); else printf(calulation has finished!n); getchar(); flag=1; break; case 3: if(flag) printf(#%s=%lfn,str,result); getchar(); break; case 4: break; if(num=4) break; int menu(void) int num; printf(%20c1-input expressionn, ); printf(%20c2-calculation expressionn, ); printf(%20c3-print resultn, ); printf(%20c4-Quitn, ); printf( please select 1,2,3,4:); do scanf(%d,&num); while(num4); return(num); 袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃螈聿蒄葿袁羁莀蒈羃膇芆蒇