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

摘 要通过数据结构这门课程，我们较深入的了解到了栈，栈是一种重要的线性结构，它广泛应用于各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。本次试验我们将探索表达式求值问题，表达式求值是程序设计语言编译中的一个最基本的问题，它的实现是栈应用的又一个典型的例子。通过实在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。用一个一维数组存放从键盘输入的表达式,表达式中可包含：加（+）、减（-）、乘（*）、除（/）,括号（,）等运算符。要对输入的表达式进行检查，看是否是合格的表达式，如遇到错误则终止，不进行计算；例如：括号不配对、除数不为零等；输入的表达式可以是常量表达式，也可以是变量表达式；如果是常量表达式，则直接输出结果；如果是变量表达式，通过对变量的不断赋值，计算变量取不同值时表达式的结果。参与运算的操作数可以是整型，也可以是浮点型。关键词： 栈；先进先出；带括号的表达式；表达式求值目 录 1绪论11.1设计任务11.2设计思想11.3基础知识22采用类c语言定义相关的数据类型42.1设定栈的数据类型定义42.2设定表达式求值的抽象数据类型定义：53各模块的伪码算法73.1存放操作符的模块：73.2存放操作数的模块：73.3栈的基本操作设置模块：74函数的调用图94.1系统总结构图94.2算法模块的调用关系94.3表达式求值流程图115调试及测试125.1调试分析125.1.1调试中遇到的问题及对问题的解决方法125.1.2算法的时间复杂度和空间复杂度135.2测试结果146源程序217设 计 总 结29致 谢30参考文献311绪论 1.1设计任务（1）较熟练地掌握语言的基本内容及程序设计的基本方法与编程技巧。（2）较熟练地掌握在系统上编辑、编译、连接和运行C程序的方法。（3）通过设计一个完整程序，掌握数据结构的算法编写、类C语言算法转换成C程序并上机调试的基本方法。（4）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。（5）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。1.2设计思想表达式求值是程序设计语言编译中的一个基本问题。它的实现是栈应用的一个典型例子。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能正确解释表达式。要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：先乘除,后加减；从左算到右；先括号内,后括号外，再根据这个运算优先的规定来实现对表达式的编译或解释执行。从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.”，则直接将它们写入后缀表达式中。如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。重复上述步骤直到遇到中缀表达式的结束0，弹出栈中的所有元素并放入后缀表达式中，算法结束。通过建立函数，完成栈的表达式求值。主函数可以调用子函数，分别完成字符的输入，字符的检验，类型转换，表达式的运算和输出信息。在主函数中可以设置调用子函数，根据输入的字符的不同，做出不同的判断，输出相应的结果。算法设计：（1）算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。（2）算法输出：表达式运算结果。（3）算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 栈是一种数据结构，它按照后进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 1.3基础知识任何一个表达式都是由操作符，运算符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素。（1）堆栈又称堆栈（stack）在计算机科学中，是一种特殊的链表形式的数据结构，它的特殊之处在于只能允许在链表的一端（称为栈顶，英文为top）进行添加和删除操作。另外堆栈数据结构的实现也可以通过数组来完成。（2）严格来说堆是指Heap，程序运行时供程序员来支配的一段内存。而栈Stack,多指函数调用时候参数的相互传递存在的内存区域。由于堆栈数据结构只允许在一端进行操作，因而按照先进后出（LIFO-LastInFirstOut）的原理工作。堆栈数据结构支持两种基本操作，压栈（push）和弹栈（pop）：（3）压栈（入栈）：将对象或者数据压入栈中，更新栈顶指针，使其指向最后入栈的对象或数据。（4）弹栈（出栈）：返回栈顶指向的对象或数据，并从栈中删除该对象或数据，更新栈顶。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈应用的又一个典型例子。为了实现算符优先算法，可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：（1）首先置非运算符栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是非运算符则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。表1 算符间的优先关系+-*/（）#+_*/(#=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返回其值；DestroyStack ( &S ) 初始条件：栈S已存在。操作结果：销毁栈S。 ClearStack( &S ) 初始条件：栈S已存在。 操作结果：将S清为空栈。StackEmpty( S ) 初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE； StackLength( S ) 初始条件：栈S已存在。 操作结果：返回S的数据元素个数，即栈的长度。2.2设定表达式求值的抽象数据类型定义： 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);操作结果：计算两个操作数的运算，返回运算的结3各模块的伪码算法 3.1存放操作符的模块 struct node2 char data2; /存放操作符 node2 *next2;定义一个名为node2的存放操作符的结点，设data的数据类型为char型，data用来存放表达式中的操作符，定义一个指针next2,使它指向data里的值。 3.2存放操作数的模块struct node double data; /存放操作数 node *next;定义一个名为node的存放操作数的结点，设data的数据类型为double型，data存放的是表达式中的操作数，定义一个名为next的指针，它指向的是data里的数值。3.3栈的基本操作设置模块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，否则返回4函数的调用图4.1系统总结构图主菜单退出程序输出结果计算表达式输入表达式图4.1 系统总结构图4.2算法模块的调用关系开始NO，出现错误提示取栈顶元素建立空栈入栈入栈若s已存在插入e为新的栈顶元素若s存在并非空，用e返回s的栈顶元素若s已存在删除s的栈顶元素输入表达式计算表达式正确？Yes输出结果退出图4.2 算法关系调用图33计算表达式输出结果结 束开 始优先级比较算法operate算法存放操作字符存放操作数Input expression建立栈4.3表达式求值流程图 表达式正确 表达式不正确图4.3 程序流程图5调试及测试5.1调试分析5.1.1调试中遇到的问题及对问题的解决方法 表5.1测试列表测试项目测试用例计算结果预期结果实验结果基本测试333表达式结果为：31+2*3-4/255表达式结果为：511+223333表达式结果为：331+22*(5-3)/41212表达式结果为：122.5-3.4/2+1*22.82.8表达式结果为：2.8223256256表达式结果为：25622.5350535.250535.2表达式结果为：50535.2-2*3+4/2-4-4表达式结果为：-43*(-2-4)+2-16-16表达式结果为：-16X2+x x=31212表达式结果为：12容错测试1+2（2与（之间没有操作符2与（之间没有操作符错误提示：括号前不能直接跟操作数续表5.1 3/(2*3-6)+2除数为0除数为0错误提示：除数不能为零2+3)(-5括号不匹配括号不匹配错误提示：括号不匹配！1+1出现3个+出现3个+错误提示：操作符不能连续出现！2 22与2之间无操作符2与2之间无操作符错误提示：操作符间应运操作符!1#1#是非法字符#是非法字符错误提示：表达式中含有非法字符！3(2+5)3与（之间没有操作符3与（之间没有操作符错误提示：括号前不能直接跟操作数！5.1.2算法的时间复杂度和空间复杂度时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性操作还是进行入栈出栈操作n次，其时间复杂度为O(n),空间上 由于用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到数组，数组在定义时必须确定大小，在不知表达式的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。表5.2 算法的时间复杂度和空间复杂度时间复杂度空间复杂度5.2测试结果 在设计程序的过程中，出现程序不能运行，发现不能找到表达式结束的标识符，因此，在设计的时候需要认为动态的添加结束标识符#，是程序能够顺利的运行。在程序无误运行之后屏幕出现对话窗口提示，在数字提示下进行输入表达式，检查表达式，计算表达式，输出结果。图5.2 表达式1+2(运行结果图图5.2 表达式2/0运行结果图图5.2 表达式1+1运行结果图图5.2 表达式3运行结果图图5.2 表达式1=2*3-4/2运行结果图图5.2 表达式11+22运行结果图图5.2 表达式1+22（5-3）/4运行结果图6源程序#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); /如果操作数的栈是最末尾一个，则输出0if(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); int 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); 7设 计 总 结这次的课程设计让我感受颇多，我就觉得我们的这一个课题应该是一个还不错的题目，因为上课的时候我认真听了，也就是说我应该可以做好，而且像这样的问题在网络上可以找到很多相关的内容。但是在我们真正开始做的时候我却发现问题不是我想像的那么简单，我们遇到了很多的麻烦。 首先，在我们开始做的时候发现根本不知道该从什么地方下手，接着我们便开始上网查找，但是网络上的东西很多都是没有用的，于是自己开始去图书馆找资料，看了很有关栈方面的知识以后，开始对栈与队列有了一定的了解，于是在掌握了这些基础知识之上，我就对我们的课题进行分析。其次，我们发现我遇到了不少问题，但是当我们遇到不懂的问题，我就和组员一起讨论，逐步将程序的一个个功能实现。虽然设计的过程是比较辛苦的，但是当我们看到设计成功的时候我们非常的开心。毕竟这一设计是我们亲手完成的。毕竟我们从这次的课程设计中学到了很多知识。例如：栈与队列的算法，我们是经过了认真的复习，才基本掌握了。还有，我们还复习了C语言的相关知识，因为我们感觉到在编程序的时候，我们明显感觉到自己的C语言，以及数据结构方面的知识还是有所欠缺的。例如：我们的课程设计用到了文件有关方面的知识，这些知识都是我们以前比较薄弱的地方，通过此次课程设计我们更加理解了这方面的内容。这次的课程设计不仅考查了我们理论知识，更主要的是考查了我们动手实践的能力，考查了我们用C语言，数据结构编程的能力。而且还考查了我们组员分配和协作的能力。在这一周中，我们合理的分配了任务，并经过我们共同的努力才把这一课题基本完成了。从这次的课程设计中，我看到了自己的不足，首先就是比较轻浮，不能够踏踏实实的，其次，就是我个人的动手操作能力，即上机编程能力还是十分欠缺的，这还是我们平时锻炼的少所造成的。所以在以后的学习中我们要加强这方面的锻炼，为我们走上社会打下坚实的基础。所以此次的课程设计对我来说意义重大。致 谢经过这两周的课程设计，我们获得了许多在课堂上听课而不能获得的知识，首先我们要感谢学校给我们安排的这次的算法与数据结构程序设计实习，然后我要感谢老师们对我们热心的指导和帮助，是他教会了我们怎样解决问题的方法，这样我们的软件设计才会更加顺利地进行，并且充分掌握了设计程序的方法。我们还要感谢许多同学的帮助，他们的帮助对于我们来说也是必不可少的。总之，是有了他们的帮助，我们才能顺利地完成软件设计，在这里我们要向他们说一句：谢谢，非常感谢！你们辛苦了！参考文献1严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社3William Ford,William Topp .DATA STRUCTURE WITH C+.清华大学出版社（影印版）4谭浩强.c语言程序设计. 清华大学出版社5张铭,刘晓丹译.数据结构与算法分析（Java版）.A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 电子工业出版社 2001 年1月目录第一章项目基本情况3一、项目情况说明3二、可行性研究的依据5第二章项目建设的必要性与可行性8一、项目建设背景8二、项目建设的必要性9三、项目建设的可行性14第三章市场供求分析及预测17一、项目区生猪养殖和养殖粪污的利用现状17二、禽畜粪污产量、沼气及沼肥产量调查与分析18三、项目产品市场前景分析20第四章项目承担单位的基本情况21一、养殖场概况21二、资产状况21三、经营状况21第五章项目地点选择分析23一、选址原则23二、项目选点23三、项目区建设条件24第六章工艺技术方案分析27一、污水处理模式的选择27二、处理工艺的选择29三、项目工艺流程31四、主要技术参数35五、主要设备选型39第七章项目建设目标40一、项目建设目标40二、项目建设规模40第八章项目建设内容42一、建安工程42二、仪器设备46第九章投资估算和资金筹措48一、投资估算的范围48二、投资估算的依据48三、投资估算49四、资金使用计划54五、资金筹措54第十章建设期限和实施进度安排55一、项目建设期限55二、项目实施进度安排55第十一章土地、规划和环保57一、土地与规划57二、环境保护57三、安全防护60第十二章项目组织管理与运行63一、项目建设组织管理63二、项目建成后运行管理66三、项目运行费用67第十三章效益分析与风险评价69一、经济效益分析69二、项目风险评价72三、生态效益75四、社会效益76五、附表77第十四章招标方案78一、编制依据78二、招标范围78三、招标方式78四、招标组织形式79有关证明材料及附件81