数据结构课程设计--用栈求表达式

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构课程设计报告课设题目： 利用栈计算简单表达式 专 业： 汽车电子工程 班 级: T1323-14 姓 名： 华胜 完成日期: 2015-01-16 指导教师: 付勇智 目录1.课程设计题目与内容32.需求分析32.1要求42.2任务描述42.3运行环境42.4开发工具33.总体设计4 3.1设计任务与目标4 3.2程序中的功能函数5 3.3方案设计与论证54算法说明6 4.1程序所含函数6 4.2函数间的调用关系74.3函数调用详细说明84.4函数流程图85详细设计说明95.1数据结构设计9 5.2模块接

2、口设计106.程序运行10 6.1 函数主界面10 6.2 计算表达式11 6.3保存结果136.4查看记录146.5清空记录166.6几种输入错误176.7程序退出197.编程心得与体会198.程序源代码21利用栈计算表达式1.题目描述及其要求：栈是计算机中常用的一种数据结构，具有广泛的使用。利用栈的性质及其操作原理编写一个使用栈计算表达式的程序有助于更好的掌握栈的使用规则和原理应用。数据结构课程设计是理解和掌握数据结构的重要环节，主要任务是实现各种数据组织中的数据逻辑结构、存储结构以及有关操作的算法。使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储

3、结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养学生的数据抽象能力和软件设计的能力。通过全部过程培养和锻炼学生的钻研能力、动手能力、分析问题和解决问题的实际能力。题目要求：(1)按照分析、设计、编码、调试、测试的软件过程完成这个应用程序。(2)为各项操作功能设计一个菜单，应用程序运行后，先显示这个菜单，然后用户通过菜单项选择希望进行的操作项目。输入要求： (1)应用程序运行后在屏幕上显示一个菜单。用户可以根据需求，选定相应的操作项目。进入每个操作后，根据应用程序的提示信息，从键盘输入相应的信息。程序根据用户输入的信息完成相应的处理，实现要求

4、的功能。(2)能对输入的数据进行简单的校验。输出要求： (1)应用程序运行后，要在屏幕上显示一个菜单。 (2)要求用户输入数据时，给出清晰、明确的提示信息，包括输入的数据内容、格式以及结束方式等。(3)在程序完成处理后，要清楚地给出程序的处理结果：如：从键盘输入一个表达式，屏幕要输出正确结果。实现要求： 采用模块化程序设计的方法，将程序中的各项功能用函数实现。2.需求分析2.1要求1) 遵循软件开发过程的基本规范；能灵活应用，具备运用数据结构知识和C语言编程解决实际问题的能力。2) 运用结构化程序设计方法，按照课程设计题目要求，完成包括需求分析、数据结构设计、概要设计、详细设计、编写代码、调试

5、和测试C程序等过程。3) 学会利用数组、结构体、链表进行相关信息表示。4) 功能模块划分清晰，系统结构图符合功能操作要求，且有详尽的功能描述5) 各主要功能模块有详尽的流程图及描述，用函数的形式实现，且调用入口、功能、出口等关系正确。6) 所设计的C程序较好的可读性和可靠性；程序书写风格规范，注释清晰。7) 界面友好（良好的人机互交），凡需要输入信息时，都有较详尽的提示信息，并对输入信息有较完善的值域分析。8) 程序经上机调试通过，不应出现语法型、功能型错误，并获得满意的结果。9) 学会通过各功能性测试用例测试程序的能力，尽可能避免原则性错误的出现。10) 掌握编写、调试和测试C语言程序的基本

6、技巧，充分理解结构化程序设计的基本方法。11) C语言课程设计报告的内容反应实际设计过程，且符合格式要求，条理清晰，内容充实。2.2任务描述（1）能从键盘输入一个数学表达式。（2）能计算一个数学表达式。（3）能保存一个数学表达式。（4）能读取保存的记录。（5）能清空已保存的记录。2.3运行环境1) Windows XP/ 7系统2) VC+6.0编译环境2.4开发工具C语言3.总体设计3.1设计任务与目标编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式，以“=” 号结束表达式。2、分析该表达式是否合法：（1）是数字，则

7、判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3）若是其它字符，则返回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并在屏幕上打印处理结果。附加功能：1. 规定表达式的合法性2. 小数计算3. 计算记录的保存与查看4. 判断表达式的合法性（1）规定表达式的合法性，括号配对，不能出现“6+3”、“6+3”等符号重叠的情况。（2）表达式开头只能是数字或“（”，表达式中只能有一个“=”。3.2程序中的功能函数：void initstack()：初始化堆栈int check()：语法检查并计算int Pu

8、sh (czs *nu, double da)：将操作数压入堆栈char procede(char top,char code)：处理操作码int change_opnd(char code)：将字符型操作码转换成优先级int push (czm *op,char co)：将操作码压入堆栈char pop (czm *op)：将操作码弹出堆栈double caculate(czm *op,czs *nu)：简单计算+，-，*，/double Pop (czs *nu)：弹出操作数3.3方案设计与论证1. 定义一个expression全局表达式结构体EXPRESS 1000存放计算过的表达式(e

9、xpress MAXSIZE)和计算结果(result)、一个计量器(i)、一个表达式字符串、一个操作码栈和一个操作数栈；2. 把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；3. 第一个字符只能是数字或“（”，最重一个字符只能是“=”；4. 表达式括号必须配对，中间不能出现“=”；5. 在“（”前面只能是“+、*、/、( ”，在“+、*、/、=、)”前面只能是数字或“）”；6. 把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；7. 把字符根据运算优先级别选择操作；8. 把表达式中的数值部分字符串转成数值压入操作数栈；9. 是“(”直接压入到操作码栈，级别比操作码

10、栈顶元素高的，把运算符压入操作码栈；10. 级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；11. 是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；12. 最后计算出结果并将其存放在EXPRESS i，计量器加1；13. 重复计算后，将结果保存在文件里，并统计计算次数；14. 查看多次计算结果，以表形式输出；15. 查看本次计算记录，以表形式输出；16. 清除计算记录，重新计算。4算法说明4.1程序所含函数：主要函数：void main()/主函数void stack1(czm *op,czs *nu)/

11、程序主菜单void stack2(czm *op,czs *nu)/第二层计算选择，子菜单void load()/显示所有计算记录void save()/保存计算结果void shown()/显示本次计算结果void result(czm *op,czs *nu)/计算结果double caculate(czm *op,czs *nu /简单计算+，-，*，/表达式处理函数：int check()/语法检查double change_num(char str)/数字字符串转成double型数字char procede(char top,char code)/处理操作码，判断栈的操作int ch

12、ange_opnd(char code)/字符型操作码转换优先级，非表达式字符返回-2栈操作函数：double Get (czs *nu)/查看操作数栈栈顶double pop (czs *nu)/操作数栈出栈int Push (czs *nu,double da)/压入操作数栈int Empty (czs *nu)/判空void Initstack(czs *nu) /初始化栈char get(czm *op)/查看栈顶char pop(czm *op)/出栈int push(czm *op,char co)/压栈int empty(czm *op)/判空void initstack(czm

13、 *op)/初始化栈4.2函数间的调用关系：l main()：主函数 stack1();load() stack1();l stack1()程序模式函数清空文件exit();check()result(op,nu) stack2()stack1(); load stack1();l stack2()子菜单 save() stack2(); shown() stack2();l result(op,nu)计算结果initstack(op) Initstack(nu) push (op,=) Push (nu,change_num(str2);change_opnd(*ps) push (op,*

14、ps)；procede(get (op),*ps) pop (op); Push (nu,caculate(op,nu)l caculate(op,nu) b=Pop (nu) a= Pop (nu) pop (op)4.3函数调用详细说明 main()函数：调用了一个函数stack1()，stack1()判断执行查看所有计算记录函数load()，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法check()并计算表达式result(op,nu)的操作。 result(op,nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断change_opnd(*ps)，若是数字，则

15、调用转化数字change_num(str2)然后压入操作数栈，若是运算符，刚调用判断操作procede(get (op),*ps)，若是“”，则弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算caculate(op,nu)后再压入操作数栈，计算完毕后按stack1()顺序运行。 stack2()函数：在计算结果后调用跟随的选择菜单，进行查看结果shown()、保存结果save()、查看计算记录load()、回到主菜单的操作。4.4函数流程图:load()main()Stack1()result()save()Check()Exit()Start2()shown()5详细设计说明5.1数

16、据结构设计1）表达式可以用一个字符串表示，计算结果可以用一个双精度浮点数即小数表示，结构简单，可以使用一段连续的地址空间，故定义一个结构体表示即可。定义如下： struct expression/表达式结构double result;char expressMAXSIZE;EXPRESSN;2）使用栈计算表达式时可以定义两个栈存放数字的操作数栈（czs）和存放计算字符（+、-、*、/、(、)）的操作码栈（czm）。它们的定义如下： typedef struct/操作码栈定义char codeMAXSIZE;int top;czm;typedef struct/操作数栈定义double data

17、MAXSIZE;int top;czs;3）宏定义：在本程序的开头定义了两个宏定义变量，用来对后面出现的相同变量进行替换。#define MAXSIZE 1000#define N 10004）全局变量：int i=05.2模块接口设计系统以主函数void main()为入口，通过调用void warning()函数，提示用户使用该程序应注意的问题，通过调用void stack1()函数，导入程序调用，系统接收用户输入的选择，调用相应的函数，进入到下一级菜单进行相关工作。6.程序运行6.1 函数主界面6.2 计算表达式6.3保存结果6.4查看记录6.5清空记录6.6几种输入错误6.7程序退出7

18、编程心得及体会数据结构、高级语言和算法设计与分析这三门课程是构成程序设计理论底层的黄金三角形。数据结构重点讨论程序设计中如何分析、规划和存储实现相关的数据以及关系。数据结构详细介绍了程序设计中各种常见的数据存储结构，对于程序设计有着至关重要的作用。如果说理论课是学习和掌握各种数据结构的存储关系及逻辑关系，那么课程设计就是对知识掌握程度的一种检测。“学而不思则罔，思而不学则殆”，学习是为了掌握知识，也为了应用于实际。一周的课程设计实践，在同学和老师的帮助下，我完成了既定的任务，实现了要求的程序功能，这使我对数据结构及编程有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的实际操作才能更好

19、地学习它。通过课程设计这一实践环节，加深了我对本学期所学知识的理解，也提高了我运用所学知识分析问题和解决实际问题的能力。在此过程中我 也发现自己好多不足之处，首先是自己对语言的一些标准库函数不太了解，其次，对于数据结构的把我也不够深刻，如栈的常见操作，还有对函数调用的正确使用不够熟悉，有时对语言中经常出现的错误也不了解，通过实践，我在这几个方面的认识有所提高。通过这一周的实践学习，我不仅认识和体验了按照分析、设计、调试和测试的软件开发过程，更从中深刻认识到了“世上无难事，只要肯攀登”的道理。虽然自己在此过程中曾花费大量时间去修改一个小错误，但是当最后看自己的程序完成了既定的任务时，当看着程序一

20、步步实现自己的想法时，心中成功的喜悦之情真是难于言表，凭此不懈的精神奋斗，还有什么困难能拦得住自己前进的步伐呢？老师说“我要的不是你们的程序，而是你们能有所收获。”“课设是帮助你们掌握所学知识的良好途径。”也许我们所学的数据结构知识对于编程来说至少冰山一角，想要达到一般程序员的水准也需要一个漫长的过程，只要你愿意学，就一定能有所收获和成就。这次的课程实践虽然很苦，但快乐也有。多掌握一门知识，对我们的学习和生活一定有重要的帮助。数据结构这门课固然难学且枯燥，很多内容太过抽象，很多数据结构类型需要通过画示意图才能理解，如栈。前人为我们树立了榜样，我们也要努力前行。8.程序源代码#include #

21、include #include #include #define MAXSIZE 100#define N 1000int i=0;/表达式数struct expression/表达式结构double result;char expressMAXSIZE;EXPRESSN;/表达式的一个整体容器stypedef struct/操作码栈定义char codeMAXSIZE;int top;czm;typedef struct/操作数栈定义double dataMAXSIZE;int top;czs;/-操作数栈栈操作-：void Initstack(czs *nu)nu-top=-1;int

22、Empty(czs *nu)/判空if(nu-top=-1)return 0;else return 1;int Push(czs *nu,double da)/压栈if(nu-top=MAXSIZE-1)printf(提醒:操作数栈已满.);return 0;nu-top+;nu-datanu-top=da;return 1;double Pop(czs *nu)/出栈double a=0;if(nu-top=-1)printf(提醒:操作数栈已满.);return a;a=nu-datanu-top;nu-top-;return a;double Get(czs *nu)/查看栈顶if(n

23、u-top!=-1)return nu-datanu-top;return 0;/-操作码栈栈操作-：void initstack(czm *op)/初始化栈op-top=-1;int empty(czm *op)/判空if(op-top=-1)return 0;else return 1;int push(czm *op,char co)/压栈if(op-top=MAXSIZE-1)printf(操作码栈已满.);return 0;op-top+;op-codeop-top=co;return 1;char pop(czm *op)/出栈char a=0;if(op-top=-1)print

24、f(提醒:操作码栈是空的.);return a;a=op-codeop-top;op-top-;return a;char get(czm *op)/查看栈顶char a=0;if(op-top=-1)printf(提醒:操作码栈是空的.);return a;elsereturn op-codeop-top;/-结束栈定义操作-/-函数操作-：int change_opnd(char code)/将字符型操作码转换成优先级，非表达式字符反回-2switch(code)case =:return 1;break;case ):return 2;break;case +:return 3;brea

25、k;case -:return 3;break;case *:return 4;break;case /:return 4;break;case (:return 0;break;/操作码级别=0;case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:case 0:case .: return -1;/操作数级别=-1；default: return -2;/其它符号级别=-2char procede(char top,char code)/处理操作码，判断栈的操作if(change_opnd(code)=0)/(入栈re

26、turn ();elseif(change_opnd(code)=2 & change_opnd(top)=0)/(和)同时出现，(出栈，)不入栈return (=);elseif(change_opnd(code);elsereturn ();/入栈double change_num(char str)/数字字符串转成double型数字char *s=str;int i,j;int p=1,q=0;/p=小数点前位数，q=小数点后位数char d=.,z=0;double da=0;if(strstr(str,d)=0)/判断是否有小数点p=strlen(str);elseif(strstr

27、(str,d)=str)/没有输入小数点前的数，如.032p=1;q=strlen(str)-1;strcpy(str,strcat(z,str);elsep=strstr(str,d)-str;q=strlen(str)-p-1;for(i=0;ip;i+)/小数点前的各位数乘以各自的阶数，然后叠加：123=1*100+2*10+3*1da=da+(int)stri-48)*pow(10,p-i-1);for(j=0;j0|*p=.)if(change_opnd(*p)!=3)printf(n表达式只能以数字或(开头,请重新输入:);gets(EXPRESSi.express);p=EXPR

28、ESSi.express;n=0;continue;elseif(change_opnd(*p)=-2)printf(n表达式%c为非法字符.请重新输入:,*p);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;else/合法刚跳到下一个字符p=p+1;continue;if(change_opnd(*p)=0)/(前一个字符只能是+、-、*、/、(if(change_opnd(*(p-1)3&change_opnd(*(p-1)!=-2)if(change_opnd(*(p-1)!=0)printf(n表达式%c不符合语法.请重新

29、输入:,*p);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;if(change_opnd(*p)=2) / )后面只能是+ - * / =if(change_opnd( *(p+1) )=0)printf(n表达式%c或%c不符合语法.请重新输入:,*p,*(p+1);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;if(change_opnd(*p)=-1)/+、-、*、/、=、)前一个字符只能是数字和)if(change_opnd(*(p-1)=2)printf(

30、n表达式%c或%c不符合语法,请重新输入:,*(p-1),*p);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;if(change_opnd(*p)=4)if(change_opnd(*(p-1)!=-1) if(change_opnd(*(p-1)!=2)printf(n表达式%c或%c不符合语法,请重新输入:,*(p-1),*p);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;if(change_opnd(*p)=1)/判断表达式中是否有=重复出现，最后括号是否配

31、对if(*(p+1)!=0)printf(n表达式中=,只能出现在表达式结束处.请重新输入:);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;if(n!=0)printf(n表达式括号不配.请重新输入:);gets(EXPRESSi.express);p=EXPRESSi.express;n=0;continue;p=p+1;return 1;double caculate(czm *op,czs *nu)/简单计算+，-，*，/double b=Pop(nu),a=Pop(nu);switch(pop(op)case +:ret

32、urn(a+b);break;case -:return(a-b);break;case *:return(a*b);break;case /:return(a/b);break;return 0;void result(czm *op,czs *nu)/计算结果char str2MAXSIZE=,str32=0;char *ps=EXPRESSi.express;initstack(op);/初始化栈Initstack(nu);push(op,=);while(!(*ps=)&(get(op)=)/检查是表达式和操作码是否到尾if(change_opnd(*ps)=-1)/操作数处理whil

33、e(change_opnd(*ps)=-1)strncpy(str3,ps,1);/数字字符一个个取出放在str2strcat(str2,str3);ps+;Push(nu,change_num(str2);strcpy(str2,);else /操作码处理switch(procede(get(op),*ps)case :Push(nu,caculate(op,nu);continue;break;if(*ps=)&get(op)=)ps+;continue;if(*ps=|get(op)=)continue;/表达式和操作码有一个到尾，则跳出继续循环ps+;EXPRESSi.result=G

34、et(nu);printf(nt 表达式:%st计算结果:%lfn,EXPRESSi.express,EXPRESSi.result);printf(t-n);i+;/表达式个数加1；void shown()/显示计算结果int n;for(n=0;n0;n-)/记录最后一个#号位置，即未保存的结果的开始位置,重复保存只会追加if(EXPRESSn-1.express0=#)break;strcpy(EXPRESSi.express,#表达式个数：);/每次保存都统计计算次数EXPRESSi.result=i-n;i+;for(m=n;mi;m+)if(fwrite(&EXPRESSm,siz

35、eof(struct expression),1,fp)!=1)/将表达式和计算结果存到文件中printf(file write errorn);fclose(fp);printf(*提醒:计算记录已经保存n);void load()/显示所有计算记录int m;struct expression eN;FILE *fp;printf(n);if(fp=fopen(calculate.dat,rb)=NULL)/空文件printf(n-n);printf(*提醒:没有记录信息,请进行计算并保存信息:n);return;for(m=0;fread(&em,sizeof(struct expression),1,fp);m+)/按照expression结构一个个读取printf(n%d -n,m+1);printf(t 表达式:%st计算结果:%.2lfn,em.express,ei.result);if(em.express0=#)/控制输出不同次计算的记录m=-1;printf(n);printf(n-n);fclose(fp);printf(n);void warning()printf(n-提示-n);printf(计算表达式时,请用户正确输入表达式,不得出现非法字符及字符重复出现n);printf(表达式以