表达式求解课程设计

《表达式求解课程设计》由会员分享，可在线阅读，更多相关《表达式求解课程设计（29页珍藏版）》请在装配图网上搜索。

1、摘 要本程序是关于表达式求解的问题，其主要功能是进行简单的四则运算 ，其特点之一是支持带括号的四则运算；二是用到栈的一些相关操作，不但对操作有提示，还对与异常输入信息报错。通过该题目的设计过程，可以加深理解线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。在表达式求解用到的算法中，c语言算法可读性很强，一方面，是因为c语言是高级语言，是面向程序员的语言，二是c语言的功能是很完备的，可以达到事半功倍的效果，和其他语言相比量是比较少。栈的应用使该程序更出色。关键字：堆栈，初始化栈，

2、入栈，出栈。 AbstractThis program is about expression to solve the problem, its main function is to carry out operations of four simple, one of its features is support four operations with brackets; two is the number of operations used stack, not only has the cue for the operation of abnormal input inform

3、ation, and error.Through the design process of the subject, to deepen understanding of the logical structure, storage structure of linear table and stack, mastering the linear table and the stack to achieve the basic operation, to further understand and master the various data structures in the book

4、, learn how to learn knowledge to solve practical problems, to cultivate students ability.In the expression used in solving algorithm, the algorithm C language readability is very strong, on the one hand, because the C language is a high-level language for programmers, the language, the two is the C

5、 language function is complete, can achieve a multiplier effect, and the amount is less than any other language. Stack of applications make the program more outstanding.Keywords: initialize the stack, stack, the stack, the stack.目录摘 要11概述41.1开发背景41.2开发意义41.3内容与要求42概要设计52.1算法时间和空间性能分析52.2模块功能图53详细设计7

6、3.1函数关系调用模块73.2用C语言构造运算符栈函数73.3用C语言构造运算数栈函数94调试分析124.1调试中遇到的问题及对问题的解决方法124.2测试结果的输出12总 结16参考文献17致 谢18附录（源程序）：191概述1.1开发背景在c语言和c+的环境中，综合数据结构所学的知识，开始将#入操作符栈，通过一个函数来判别算术运算符的优先级。且规定#的优先级最低。在输入表达式的最后输入#，代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈。遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,

7、进行运算,所得结果入数栈,重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。编写出对应的程序来实现它。1.2开发意义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间相互关系及操作的学科。数据结构按其元素之间的关系可分为四种：1.集合2.线性结构3.树形结构4.网状结构。而栈作为一种重要的线性结构，从数据结构的角度看，其特殊性在于其操作是线性表操作的子集。她是操作受限的线性表。因此可称其为限定性数据结构。但从数据类型的角度看，它是与线性表大不相同的一类重要的抽象数据类型。由于其后进先出的特性，被广泛地应用于各种软件系统

8、中。1.3内容与要求（1）使用顺序栈存储算术表达式，主要功能有：输入并建立算术表达式、输出算术表达式、算术表达式的计算及显示输出等； （2）至少要用10个测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；（4）假设算术表达式中只含加减乘除等四种运算符，操作数是实数，界限符有括号有“（）”、“”、“ ”、表达式起始、结束符“#”等；（5）要求对自己设计的程序进行多次的调试；若表达式在输入出错时能够提示并进行修正；显示栈的变化过程。（6）通过本次程

9、序设计，更好的掌握建栈、入栈和出栈的顺序，深化数据结构所学的基本内容，提高自己的程序设计能力和编写能力。2概要设计2.1算法时间和空间性能分析时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于在本程序中，在为算符栈(OPTR)和操作数栈(OPND)涉及到两种情况时申请空间，一方面分别为OPTR栈和OPND栈申请了初始的存储单元，均为STACK_INITSIZE=100个；另一方面，考虑到两个栈在处理具体的算术表达式时，有可能会出现溢出的情况，即栈的初始的存储空间不够用，这时需要为其申请额外的存储空间，每溢出一次，就为其

10、申请存储单元STACKINCREMENT=10个；所以，本程序的算法的空间复杂度一方面取决于算术表达式的长度，另一方面取决于本程序的所有代码所占用的存储空间大小。2.2模块功能图设计一个程序，首先要了解程序的设计思路和程序的基本构成框架，图2.1为设计程序的基本思路和概要，通过逐步的模块间的关系调用来实现整个程序的完整性：主程序模块栈的建立及初始化模块判断输入是否结束模块判断字符类型模块输入结束输出结果运算符进栈模块运算符运算数出栈模块运算模块运算符优先级比较模块运算数进栈模块图2.1模块功能图3详细设计3.1函数关系调用模块下图是各函数间的调用关系图，主要是将各个函数间的调用和程序中用到的函

11、数用图形的形式表现出来，可以更好地理解程序中各个函数的用法。GetTopCalculatePrecedePopDispStackPushInitStackEvaluatemain图3.1函数关系调用图3.2用C语言构造运算符栈函数该模块是用C语言构造出运算符栈函数，首先构造一个空运算符栈，并分配空间，然后实现运算符进栈、出栈等等运算符的栈操作。void Optr_InitStack(Optr_Stack &S1)/构造一个空运算符栈S1S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char);if(!S1.base)cout=S1.stacksi

12、ze)/如果栈满，追加存储空间S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char);if(!S1.base)cout存储分配失败！;elseS1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;*S1.top=e;S1.top=S1.top+1;/将运算符压入栈中，指针上移char Optr_GetTop(Optr_Stack &S1)/取栈顶运算符char e;if(S1.top=S1.base)coutnttt运算

13、符栈已空!n;else e=*(S1.top-1);return e;void Optr_DispStack(Optr_Stack &S1)/从运算符栈底到栈顶依次输出各运算符char e,*p;if(S1.top=S1.base)cout ;elsep=S1.base;while(pS1.top)e=*p;p+;coute;char Optr_Pop(Optr_Stack &S1)/运算符出栈char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;e=*(-S1.top);return e;3.3用C语言构造运算数栈函数该模块是用C语言构造出运算符栈函数，首先构造

14、一个空运算符栈，并分配空间，然后实现运算数进栈、出栈等等运算数的栈操作。void Opnd_InitStack(Opnd_Stack &S2)/构造一个空运算数栈S2S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float);if(!S2.base)cout=S2.stacksize)/栈满，追加存储空间S2.base=(float*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout存储分配失败！;elseS2.top=S2.base+S2.

15、stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;*S2.top=e;S2.top=S2.top+1;/将数e入栈，指针上移void Opnd_DispStack(Opnd_Stack &S2)/从运算数栈底到栈顶依次输出各元素float e,*p;if(S2.top=S2.base)cout ;elsep=S2.base;while(pS2.top)e=*p;p+;coute;float Opnd_GetTop(Opnd_Stack &S2)/取栈顶元素float e;if(S2.top=S2.base) coutntt运算数栈已空!;el

16、se e=*(S2.top-1);return e;float Opnd_Pop(Opnd_Stack &S2)/出栈float e;if(S2.top=S2.base)coutntt运算数栈已空!;e=*(-S2.top);return e;4调试分析4.1调试中遇到的问题及对问题的解决方法本程序一开始面临精确度不高的问题，具体说 就是它只能计算整数，对于小数它会报告输入错误，这种性能缺陷是致命的，打个比方，就像一个大个子，长了两只很短的胳膊。对此，我 定义操作数类型时，将原来的int型改为float型和double型4.2测试结果的输出对任意一组（66与44）实数的四则运算的计算结果和计算

17、过程中栈的变化过程的输出。图4.1为66+44的输出结果与程序逐步运行图图4.2为6644的输出结果与程序逐步运行图图4.3为66-44的输出结果与程序逐步运行图图4.4为6644的输出结果与程序逐步运行图总 结两周的课程设计，对我来说是很大的考验，在这次课程设计中我对整个程序主体结构的设计、界面的设计、部分算法功能代码的编写还不太熟练，因为很多程序段、函数的定义和调用及用法在平时的学习中已可能被我遗忘，并且在以往学习的过程中我对c语言编程中的常用语句、循环结构、过程也并未完全掌握，但是在学习设计的过程中我发现许多数据结构中的算法都是有一定的相似之处的，我主要查看了线性表及栈的逻辑结构、存储结

18、构，线性表及栈上的基本运算。加上老师和同学们的帮助，我才能够在短时间的期限内可以勉强完成设计任务。本次课程设计我们从一开始的选题到现在的设计结束，前前后后将近半个月时间。在这期间，我从c语言课本和数据结构课本上熟悉和巩固了许多基本知识，也掌握了一些新的知识点，通过这次课程设计，我不仅对课本的基本知识有了一定的掌握，还对其他方面的知识也有所了解，这些将为我以后的课程设计埋下扎实的基础，让我有不小的收获！参考文献 1严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3 DATA STRUCTURE WITH C+. William F

19、ord,William Topp .清华大学出版社（影印版）. 4谭浩强.c语言程序设计. 清华大学出版社. 5数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月致 谢本次课程设计能够顺利完成首先感谢我的指导老师，杨老师老师在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。第二，我要感谢我的数

20、据结构老师贾娟娟老师，在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。我的同学也对我进行了一系列的帮助，没有他们，也许就难以发现一些潜在的错误，在此表示感谢。附录（源程序）：#includeusing namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct /运算符栈char *base;char *top;int stacksize;Optr_Stack;typedef struct /运算数栈float *base;float *top;int stack

21、size;Opnd_Stack;void Optr_InitStack(Optr_Stack &S1);/声明栈建立运算符函数void Opnd_InitStack(Opnd_Stack &S2);/声明栈建立运算数函数void Evaluate(Optr_Stack &S1,Opnd_Stack &S2);/声明确定如何入栈函数void Optr_Push(Optr_Stack &S1,char e);/声明运算符入栈函数void Opnd_Push(Opnd_Stack &S2,float e);/声明运算数入栈函数char Optr_GetTop(Optr_Stack &S1);/声明取

22、运算符栈顶元素函数float Opnd_GetTop(Opnd_Stack &S2);/声明取运算数栈顶元素函数char Optr_Pop(Optr_Stack &S1);/声明运算符出栈函数float Opnd_Pop(Opnd_Stack &S2);/声明运算数出栈函数char Precede(char m,char n);/声明运算符优先级比较函数float Calculate(float a,char rheta,float b);/声明运算表达式函数void Optr_DispStack(Optr_Stack &S1);/从运算符栈底到栈顶依次输出各运算符/*主函数*/int mai

23、n() Optr_Stack S1;/定义运算符栈 Opnd_Stack S2;/定义运算数栈/freopen(data1.in,r,stdin);/freopen(data1.out,w,stdout);int flag=1;while(flag)/可以反复进行算术表达式的求值 int m; Optr_InitStack(S1);/调用运算符栈建立函数 Opnd_InitStack(S2);/调用运算数栈建立函数Evaluate(S1,S2);/输入字符表达式确定如何入栈函数cout请问是否继续算术表达式求值：0:否 1:是endl;/与用户进行简单的会话是否继续，输入1就继续，0就退出co

24、utm;flag=m;return 0;/*运算符栈函数*/void Optr_InitStack(Optr_Stack &S1)/构造一个空运算符栈S1S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char);if(!S1.base)cout=S1.stacksize)/如果栈满，追加存储空间S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char);if(!S1.base)cout存储分配失败！;elseS1.top=S1.base+S1.stacksiz

25、e;S1.stacksize=S1.stacksize+STACKINCREMENT;*S1.top=e;S1.top=S1.top+1;/将运算符压入栈中，指针上移char Optr_GetTop(Optr_Stack &S1)/取栈顶运算符char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;else e=*(S1.top-1);return e;void Optr_DispStack(Optr_Stack &S1)/从运算符栈底到栈顶依次输出各运算符char e,*p;if(S1.top=S1.base)cout ;elsep=S1.base;while(p

26、S1.top)e=*p;p+;coute;char Optr_Pop(Optr_Stack &S1)/运算符出栈char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;e=*(-S1.top);return e;/*运算数栈函数*/void Opnd_InitStack(Opnd_Stack &S2)/构造一个空运算数栈S2S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float);if(!S2.base)cout=S2.stacksize)/栈满，追加存储空间S2.base=(float*)realloc(S2.b

27、ase,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout存储分配失败！;elseS2.top=S2.base+S2.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;*S2.top=e;S2.top=S2.top+1;/将数e入栈，指针上移void Opnd_DispStack(Opnd_Stack &S2)/从运算数栈底到栈顶依次输出各元素float e,*p;if(S2.top=S2.base)cout ;elsep=S2.base;while(pS2.top)e=*

28、p;p+;coute;float Opnd_GetTop(Opnd_Stack &S2)/取栈顶元素float e;if(S2.top=S2.base) coutntt运算数栈已空!;else e=*(S2.top-1);return e;float Opnd_Pop(Opnd_Stack &S2)/出栈float e;if(S2.top=S2.base)coutntt运算数栈已空!;e=*(-S2.top);return e;/*输入表达式确定如何入栈函数*/void Evaluate(Optr_Stack &S1,Opnd_Stack &S2)char c;float t,e;int n=

29、0,i=1,j=0,k=0,l=0;char chSTACK_INIT_SIZE;int s=1;int flag=0,flag2=0;float p1,p2;char ch1;Optr_Push(S1,#);/将#入栈，作为低级运算符coutch;c=ch0;coutn对表达式求值的操作过程如下：n*n步骤t运算符栈S1t运算数栈S2t字符表达式t栈主要操作过程;while(c!=#|Optr_GetTop(S1)!=#) coutn*n; couti+t;Optr_DispStack(S1);couttt;Opnd_DispStack(S2);couttt;if(flag=1)k-;fla

30、g=0; if(flag2)k+=flag2;flag2=0;for(l=0;lk;l+)cout ;for(j=k;chj!=0;j+)cout=0)e=float(c-48);n+;if(n=1)t=e;else if(n1)t=t*10+e; /转换小数点前面的部分c=chs+;if(n=-1)e=float(c-48); /转换小数点后面的部分t=t+e/10;c=chs+; /将转换后的两部分加起来，最终转换成浮点数if(c=.)n=-1;c=chs+; if(c=0&c=9)|c=.)flag2+;goto as;if(c9) Opnd_Push(S2,t); couttOpnd_

31、Push(S2,t);else/输入的是运算符n=0;/非运算型数据计数器清零switch(Precede(Optr_GetTop(S1),c)/比较运算符的优先级case :/栈顶元素优先级低，则入栈且继续输入Optr_Push(S1,c);couttOptr_Push(S1,c);c=chs+;break;case =:/栈顶元素优先级相等，脱括号并接收下一字符Optr_Pop(S1);cout:/栈顶元素优先级高，则退栈并将运算结果入栈p1=Opnd_Pop(S2);p2=Opnd_Pop(S2);ch1=Optr_Pop(S1);Opnd_Push(S2,Calculate(p2,ch

32、1,p1);couttCalculate(p2,ch1,p1);flag=1;break;coutn*n;coutit#ttOpnd_GetTop(S2)tt;for(j=0;jk;j+) cout ;cout#tRETURN(GETTOP(S2);coutn*n;if(S2.top-1=S2.base)/显示表达式最终结果coutn表达式的结果为：Opnd_GetTop(S2)endl;else coutn表达式出错!n;char Precede(char m,char n)/运算符的优先级比较if(n=+|n=-)/输入符号为+、- if(m=(|m=#)return ;/栈顶元素为(、#

33、,此时栈顶符号优先级低，返回;/否则，栈顶符号优先级高,返回else if(n=*|n=/)/输入的符号为*、/if(m=)|m=*|m=/)return ;/栈顶元素为)、*、/,此时栈顶符号优先级高，返回else return ;/否则，栈顶符号优先级低,返回else if(n=()return;/输入的符号为(,则直接返回;/否则，栈顶符号优先级高,返回else /输入符号为其他if(m=#)return=;/栈顶元素为#,此时优先级同，返回=else return ;/否则，栈顶符号优先级高,返回float Calculate(float a,char theta,float b)/运算函数float tmp=0;if (theta=+)tmp=a+b;/从运算符栈取出的符号为+，则运算数栈的两元素相加，并返回else if(theta=-)tmp=a-b;/从运算符栈取出的符号为-，则运算数栈的两元素相减，并返回else if(theta=*)tmp=a*b;/从运算符栈取出的符号为*，则运算数栈的两元素相乘，并返回else if(theta=/) /从运算符栈取出的符号为/，则运算数栈的两元素相除，并返回if(b=0) coutn表达式出错!除数不能为0!n;else tmp=a/b;return tmp;