数据结构算术表达式求值课程设计.pdf

《数据结构算术表达式求值课程设计.pdf》由会员分享，可在线阅读，更多相关《数据结构算术表达式求值课程设计.pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目目录录1 1前前言言 2 22 2问题描述问题描述 3 33 3总体设计总体设计 错误! 未定义书签。3.13.1 概要设计概要设计 错误!未定义书签。3.1.13.1.1 数据结构的选择数据结构的选择 3 33.1.23.1.2 相关功能函数相关功能函数 3 33.1.33.1.3 函数模块调用关系函数模块调用关系 4 43.23.2 详细设计和编码详细设计和编码 5 54 4运行与测试运行与测试 9 94.14.1 上机调试上机调试 9 94.24.2 算法时间和空间性能分析算法时间和空间性能分析 1 10 04.34.3 程序运行测试结果程序运行测试结果 1 11 15.5. 总结与心

2、得总结与心得 13 135.15.1 设计中难点的总结以及其它解决方案设计中难点的总结以及其它解决方案 1 13 35.25.2 实验心得实验心得 1 14 46.6. 用户使用说明用户使用说明 16 167.7. 参考文献参考文献 16 168.8. 附附 录录 1 1（源代码清单）（源代码清单） 16 169.9. 附附 录录 2 2（成绩评定表）（成绩评定表） 25 2511.前言前言课程设计是实践性教学中的一个重要环节， 它以某一课程为基础，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。 数据

3、结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。在数据结构的学习和课程设计过程中， 我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程基本内容的理解。同时， 在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高， 但是在实际操作过程中， 没有足够的专业知识对于编程来说是远远不可以达到要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是：以字符序列的形式从终端输入语法正确

4、的，不含变量的表达式。利用算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、 输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们， 同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比较困难的，以我自身的能力，是不可能在规定的时间内完成任务的， 所以我参考了很多有价值的书籍来帮助我完成我的程序设计。22. 2.问题描述（问题描述（问题分析和任务定义）在

5、计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格 地从左到右进行。因此，要求设计一个程序，利用栈演示运算符优先法对算术表达式求值的过程， 利用算符有限关系， 实现对算数混合四则运算表达式的求值。程序输入：一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量 ）。为了简化，操作数只能为浮点数，操作符 为 “ +”、“-”、“*”、“/”、“（”、“）”，用“#”表示结束。程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程。测试数据：1024/(4*8) 、(20+2)*(6/

6、2)（用于正确性检测的合法输入数据）9/0（用于健壮性检测的非法输入数据）3. 3.总体设计总体设计3.13.1 概要设计概要设计3.1.1 数据结构的选择任何一个表达式都是由操作符， 运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。首先置操作数栈为空栈，表达式起始符“”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，若是操作数则进入 OPND 栈，若是运算符，则和 OPTR 栈的栈顶运算符比较优先权

7、后做相应操作，直至整个表达式求值完毕。栈的抽象数据类型定义ADT SqStack数据对象：D=ai| ai ElemSet,i=1,2,3，n,n0数据关系：R1=| ai-1,ai D,i=1,2,3,，n约定其中 ai 端为栈底，an 端为栈顶。操作集合：见如下相关功能函数ADT SqStack3.1.2 相关功能函数运算符栈的功能函数运算符栈的功能函数OPTR 栈运算符栈的初始化void Optr_InitStack(Optr_Stack &S1)运算符栈的栈顶插入新的数据元素void Optr_Push(Optr_Stack &S1,char e)3char Optr_Pop(Optr

8、_Stack &S1)char Optr_GetTop(Optr_Stack &S1)void Optr_DispStack(Optr_Stack &S1)运算数栈的功能函数运算数栈的功能函数运算符的栈顶元素出栈取出运算符栈的栈顶元素从栈底到栈顶依次输出各运算符OPND 栈运算数栈的初始化void Opnd_InitStack(Opnd_Stack &S2)获取运算数栈的栈顶元素intGetTop2(SqStack2 &S2)运算数栈的栈顶插入新的数据元素void Optr_Push(Optr_Stack &S1,char e)运算数栈的栈顶元素出栈float Opnd_Pop(Opnd_St

9、ack &S2)voidOpnd_DispStack(Opnd_Stack从栈底到栈顶依次输出各运算数&S2)算术表达式的相关功能函数算术表达式的相关功能函数char Precede(char m,char n)float Calculate(float a,char rheta,float b)void Evaluate(Optr_Stack&S1,Opnd_Stack &S2)3.1.3 函数模块调用关系运算符的优先级比较函数运算函数判断算术表达式各字符如何入栈函数4主程序模块栈的建立及初始化模块判断输入是否结束模块判断字符类型模块运算数进栈模块运算符优先级比较模块运算符进栈模块运算符运算

10、数出栈模块运算模块输入结束 输出结果3.23.2 详细设计和编码详细设计和编码首先本程序定义两个顺序栈：运算符栈（OPTR）和运算数栈（OPND）；OPTR 栈定义如下：typedefstructchar* base;/算符栈的栈底char* top;/算符栈的栈顶intstacksize;/算符栈的最大长度Optr_Stack;OPND 栈定义如下：typedef structfloat* base;/操作数栈的栈底float* top;/操作数栈的栈顶intstacksize;/操作数栈的最大长度Opnd_Stack;然后是主要功能函数的详细设计：（1）char Precede(char

11、m,char n) 判断运算符优先权，返回优先权高的算符间的优先关系如下：12+-+-*5/（#*/（#=函数实现如下：char Precede(char m,char n)/运算符的优先级比较if(n=+|n=-)/输入符号为+、-if(m=(|m=#)return ;/栈顶元素为(、#,此时栈顶符号优先级低，返回;/否则，栈顶符号优先级高,返回else if(n=*|n=/)/输入的符号为*、/if(m=)|m=*|m=/)return ;/栈顶元素为)、*、/,此时栈顶符号优先级高，返回else return ;/否则，栈顶符号优先级低,返回else if(n=()return;/输入的

12、符号为(,则直接返回;/否则，栈顶符号优先级高,返回else/输入符号为其他if(m=#)return=;/栈顶元素为#,此时优先级同，返回=else return ;/否则，栈顶符号优先级高,返回（2）void Evaluate(Optr_Stack &S1,Opnd_Stack &S2)以字符串形式输入算数表达式，根据是运算符还是运算数来判断如何入栈函数实现如下：void Evaluate(Optr_Stack &S1,Opnd_Stack &S2)char c;float t,e;int n=0,i=1,j=0,k=0,l=0;char chSTACK_INIT_SIZE;int s=1

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

14、)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;/转换小数点前面的部分7c=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);coutttOpnd_Push(S2,t);else/输入的是运算符n=0;/非运算

15、型数据计数器清零switch(Precede(Optr_GetTop(S1),c)/比较运算符的优先级case :/栈顶元素优先级低，则入栈且继续输入Optr_Push(S1,c);coutttOptr_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,ch1,p1);coutttCalculate(p2,ch1,p

16、1);flag=1;break;coutn*n;coutit#ttOpnd_GetTop(S2)tt;for(j=0;jk;j+) cout ;cout#ttRETURN(GETTOP(S2);coutn*n;if(S2.top-1=S2.base)/显示表达式最终结果coutn 表达式的结果为：Opnd_GetTop(S2)endl;else coutn 表达式出错!n;（3）float Calculate(float a,char theta,float b)运算函数， 运用 else-if 语句， 不同的运算符则进行不同的运算； 进行除法时，若分母为 0，则将标志标记成错误。函数实现如下

17、：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) cout, , , ,$, ,$,=;i=LocateChar

18、 (c1); /定位 c1 在+、-、*、/、 (、)、# 中的位1 4序，从 0 开始计数j=LocateChar (c2); /定位 c2 在+、-、*、/、 (、)、# 中的位序，从 0 开始计数if(Pij=$) cout=0&c=9|c=.) Datai=c; i+;1 5 c=getchar(); Datai=0;/数字没有存满,输入字符串结束符 d=atof(Data);/此处是把数组里的数字（实际上是按字符串）转换为double 类型 return d; 5.25.2 实验心得实验心得通过此次课程设计，使我更加扎实的掌握了有关数据结构栈方面的知识，在设计过程中虽然遇到了一些问题

19、，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我掌握的知识不再是纸上谈兵，而且通过实际操作，我也发现我的好多不足之处：(1)用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式。开始有些茫然，后来通过结合课本和同学的帮助完成了该课题。(2)对一些看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。(3)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。这

20、不仅要求要端正自己学习的态度，更要求要对程序设计报以严谨的态度，我希望自己在以后的学习能更多的用到这些知识。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！课程设计诚然是一门专业课， 给我很多专业知识以及专业技能上的提升，

21、但它同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。同时，设计让我感触很深，使我对抽象的理论有了具体的认识，在这个过程中，我不仅培养了独立思考、动手操作的能力，还在各种其它能力上也都有了提高。更重要的是，在实践中，我学会了很多学习的方法，而这是日后最实用的，也是最受益匪浅的。要面对社会的挑战，只有不断的学习、实践，再学习、再实践，这对于我们的将来也有很大的帮助。1 6此外， 本次课程设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教老师或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获肯定也会颇丰！6.用户使用说明：用户使用说明：（1

22、）使用环境：Visual C+ 6.0.（2）操作要求：程序运行后,用户根据提示输入合法的不含变量的算术表达式，以“#”输入结束，即可以计算出结果，并看到运算符与运算数栈的操作过程，之后用户再根据提示，选择是否还要继续进行算术表达式的运算，是则继续输入，否则退出程序。7. 7.参考文献参考文献1严蔚敏，吴伟民. 数据结构（C 语言版）M.北京：清华大学版社，20072严蔚敏，吴伟民,米宁.数据结构习题集（C 语言版）M.北京：清华大学版社，20073王淑礼，王新霞.算术表达式求值算法实现的难点剖析J.福建电脑，2012年第 3 期:4唐蔼明， 谢泉钦.算术表达式程序设计算法分析J.闽江学院学报

23、， 24(2),2013年 4 月5殷人昆.数据结构（C+版）M.北京：清华大学版社，20018. 8.附录附录（源程序清单）#includeusing namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct /运算符栈char *base;char *top;int stacksize;Optr_Stack;1 7typedef struct /运算数栈float *base;float *top;int stacksize;Opnd_Stack;void Optr_InitStack(

24、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);/声明取运算符栈顶元素函数float Opnd_GetTop(Opnd_Sta

25、ck &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);/从运算符栈底到栈顶依次输出各运算符void Opnd_DispStack(Opnd_Stack &S2);/从运算数栈底到栈顶依次输

26、出各运算数/*主函数*/int main() 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;/与用户进行简单的会

27、话是否继续，输入1就继续，0就退出1 8coutm;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.t

28、op=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运算符栈已空!n;else e=*(S1.top-1);return e;void Optr_DispStack(Optr_Stack &S1)/从运算符栈底到栈顶依次输出各运算符1 9char e,*p;if(S1.top=S1.base)co

29、ut ;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;/*运算数栈函数*/void Opnd_InitStack(Opnd_Stack &S2)/构造一个空运算数栈S2S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float);if(!S2.base)cout=S2.stacksize)/栈满，追加存储空间S2.

30、base=(float*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout存储分配失败！;else2 0S2.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 ;els

31、ep=S2.base;while(pS2.top)e=*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;/*输入表达式确定如何入栈函数*/2 1void Evaluate(Optr_Stack &S1,Opnd_St

32、ack &S2)char c;float t,e;int n=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_Dis

33、pStack(S2);couttt;if(flag=1)k-;flag=0; if(flag2)k+=flag2;flag2=0;for(l=0;lk;l+)cout ;for(j=k;chj!=0;j+)2 2cout=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

34、as;if(c9) Opnd_Push(S2,t);couttOpnd_Push(S2,t);else/输入的是运算符n=0;/非运算型数据计数器清零2 3switch(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=Op

35、tr_Pop(S1);Opnd_Push(S2,Calculate(p2,ch1,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=+

36、|n=-)/输入符号为+、-2 4if(m=(|m=#)return ;/栈顶元素为(、#,此时栈顶符号优先级低，返回;/否则，栈顶符号优先级高,返回else if(n=*|n=/)/输入的符号为*、/if(m=)|m=*|m=/)return ;/栈顶元素为)、*、 /,此时栈顶符号优先级高，返回else return ;/否则，栈顶符号优先级低,返回else if(n=()return;/输入的符号为(,则直接返回;/否则，栈顶符号优先级高,返回else /输入符号为其他if(m=#)return=;/栈顶元素为#,此时优先级同，返回=else return ;/否则，栈顶符号优先级高,返

37、回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;2 5本科生课程设计成绩评定表本科生课程设计成绩评定表班级：姓名：学号：序号123456评分项目学习态度认真、遵守纪律设计分析合理性设计方案正确性、可行性、创造性设计结果正确性设计报告的规范性设计验收满分101020401010总得分/等级实得分评语：注：最终成绩以五级分制记。优（ 90-100 分）、良（ 80-89 分）、中（ 70-79 分）、及格（60-69 分）、60 分以下为不及格指导教师签名：年月日2 62 7