数据结构课程设计报告_中缀算术表达式求值

1、课 程 设 计 报 告课程名称 数据结构 课题名称 中缀算术表达式求值 专 业 通信工程 班 级 通信0902 学 号 姓 名 指导教师 2011年 07 月 01 日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 中缀算术表达式求值 专业班级 通信工程0902 学生姓名 学 号 指导老师 审 批 任务书下达日期 2011 年 06 月 27日任务完成日期 2011 年 07 月 01日设计要求：1. 课程设计报告规范（1）需求分析a.程序的功能。b.输入输出的要求。（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数

2、据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a.采用C语言定义相关的数据类型。b 写出各模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体

3、;行距为22。（7）附录源程序清单（带注释）2. 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。3 . 课程验收（1）运行所设计的系统。（

4、2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2 进度安排第 19 周：星期一 8：0012：00 上课 星期一 14：3018：30 上机星期二 14：3018：30 上机 星期四 8：0012：00 上机 附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模

5、块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在4500字以上（不含程序原代码）。 目录一、设计内容与设计要求3二、需求分析3a、程序功能3b、输入输出的要求3三、概要设计3四、详细设计3a、数据类型的定义3b：各模块的类c代码3c、程序函数：3五、调试分析与设计体会3a测试数据3b.程序调试中遇到的问题以及解决问题的方法3c.课程设计过程经验教训、心得体会3六、使用说明3六、附录3一、设计内容与设计要求（1）课题：中缀算术表达式求值（2）我们很早就学习如何书写及计算表达式，诸如：8+5*（7-3）之类的表达式，先算括号内的7减去3

6、，得到4，然后再算5乘以4，得到20，再计算8加上20，得到28，因此该表达式的值为28。这是人们熟悉的运算规则额：有括号先算括号内；无括号时，先做乘除法，后做加减法；对于相同级别的运算按从左到右的次序运算。而计算机是如何实现表达式的计算的呢？应用栈的相关知识，编程序实现之。（3）设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算术符优先关系，实现对算数四则混合运算表达式的求值，并演示在求值过程中运算符栈、操作符栈、输入字符和主要操作的变化过程。二、需求分析a、程序功能该程序能从键盘

7、从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算术符优先关系，实现对算数四则混合运算表达式的求值。(1)该程序对表达式进行求解，并对所求解的结果进行保存并附有查看功能。(2)在对表达式求解过程显示栈的变化情况，并显示表达式。b、输入输出的要求(1)从键盘输入的表达式必须满足程序所要求的。a：规定表达式的合法性，括号配对，不能出现“6+3”、“6+3”等符号重叠的情况。b：表达式开头只能是数字或“（”，表达式中只能有一个“=”。(2)要得到输出结果，必须键入回车键，根据界面的提示，键入相应的符

8、号。此外本程序的运行平台为Visual C+ 6.0版本。三、概要设计本程序的数据结构为栈。程序的主要模块可以分为运算符栈，操作数栈，以及各类函数。其中本程序的设计思路及其各模块的调用关系如下：（1）定义一个expression全局表达式结构体expr1000存放计算过的表达式(expstrMAXSIZE)和计算结果(result)、一个计量器(i)、一个表达式字符串、 一个操作码栈和一个操作数栈；（2）把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；（3）第一个字符只能是数字或“（”，最重一个字符只能是“=”；（4）表达式括号必须配对，中间不能出现“=”；（5）在“（”前面只能是

9、“+、*、/、( ”，在“+、*、/、=、)”前面只能是数字或“）”；（6）把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；(7)把字符根据运算优先级别选择操作；(8)把表达式中的数值部分字符串转成数值压入操作数栈；(9)是“(”直接压入到操作码栈，级别比操作码栈顶元素高的，把运算符压入操作码栈；(10)级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；(11)是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；(12)最后计算出结果并将其存放在expri，计量器加1；（13）重复计算后，将结

10、果保存在文件里，并统计计算次数；（14）查看多次计算结果，以表形式输出；(15)查看本次计算记录，以表形式输出；(16)清除计算记录，重新计算；程序中应主要包含下面几个功能函数：void initstack()：初始化栈int make_str()：语法检查并计算int push_num(double num)：将操作数入栈char procede(char top,char code)：处理操作码int change_opnd(int operate)：将字符型操作码转换成优先级int change_opnd(char code)：将操作码入栈char pop_opnd(opnd *op)：

11、将操作码出栈int caculate(int cur_opnd)：简单计算+，-，*，/double pop_num(num *nu)：取出操作数四、详细设计a、数据类型的定义操作码栈定义为char型，操作数栈定义为double型，计算结果定义为double型；b：各模块的类c代码本程序的数据结构为栈；1：操作码栈的c代码为:typedef struct/运算符栈的定义char codeMAXSIZE;int top;opnd;/opnd栈操作：void initstack(opnd *op)/初始化栈op-top=-1;int empty_opnd(opnd *op)/判空if(op-top

12、=-1)return 0;else return 1;int push_opnd(opnd *op,char co)/入栈if(op-top=MAXSIZE-1)printf(The opnd stack is full.);return 0;op-top+;op-codeop-top=co;return 1;char pop_opnd(opnd *op)/出栈char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;a=op-codeop-top;op-top-;return a;char get_opnd(o

13、pnd *op)/查看栈顶char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;elsereturn op-codeop-top;char Disp_opnd(opnd *op)/输出栈内元素int i;if(op-top=-1)printf(运算符栈为空!n);return 0;for(i=op-top;i=0;i-)printf(%c ,op-codei);return 1;2：操作数栈c代码如下：typedef struct/操作数栈定义double dateMAXSIZE;int top;num;/n

14、um栈操作：void initstack(num *nu)nu-top=-1;int empty_num(num *nu)/判空if(nu-top=-1)return 0;else return 1;int push_num(num *nu,double da)/入栈if(nu-top=MAXSIZE-1)printf(error:The date stack is full.);return 0;nu-top+;nu-datenu-top=da;return 1;double pop_num(num *nu)/出栈double a=0;if(nu-top=-1)printf(error:Th

15、e date stack is empty.);return a;a=nu-datenu-top;nu-top-;return a;double get_num(num *nu)/查看栈顶if(nu-top!=-1)return nu-datenu-top;double Disp_num(num *nu)/输出栈内元素int i;if(nu-top=-1)printf(数字栈为空!n);return 0;for(i=nu-top;i=0;i-)printf(%f ,nu-datai);return 1;c、程序函数：主要函数：void start(opnd *op,num *nu)/程序主菜单

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

17、hange_opnd(char code)/字符型操作码转换优先级，非表达式字符返回-2栈操作函数：double get_num(num *nu)/查看操作数栈栈顶double pop_num(num *nu)/操作数栈出栈int push_num(num *nu,double da)/入操作数栈int empty_num(num *nu)/判空void initstack(num *nu)char get_opnd(opnd *op)/查看栈顶char pop_opnd(opnd *op)/出栈int push_opnd(opnd *op,char co)/入栈int empty_opnd(

18、opnd *op)/判空void initstack(opnd *op)/初始化栈其中函数间的调用关系：l main( )：主函数 start()；load() start();l start ( )程序模式函数清空文件exit();make_str()result(op,nu) start2()start(); load start();l start2( )子菜单 save() start2(); check() start2();l result(op,nu)计算结果initstack(op) initstack(nu) push_opnd(op,=) push_num(nu,chang

19、e_num(str2);change_opnd(*ps) push_opnd(op,*ps)；procede(get_opnd(op),*ps) pop_opnd(op); push_num(nu,caculate(op,nu)l caculate(op,nu) b=pop_num(nu) a=pop_num(nu) pop_opnd(op) main( )函数：调用了一个函数start( )，start( )判断执行查看所有计算记录函数load( )，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法make_str( )并计算表达式result(op,nu)的操作。 resu

20、lt(op,nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断change_opnd(*ps)，若是数字，则调用转化数字change_num(str2)然后压入操作数栈，若是运算符，刚调用判断操作procede(get_opnd(op),*ps)，若是“”，则弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算caculate(op,nu)后再压入操作数栈，计算完毕后按start()顺序运行。 start2( )函数：在计算结果后调用跟随的选择菜单，进行查看结果check( )、保存结果save( )、查看计算记录load( )、回到主菜单的操作。主要函数流程opnd opnum

21、nuhelp()start(&op,&nu)输出界面开始结束i=0 str2MAXSIZE= str32=0char *ps=expri.expstrinitstack(op)initstack(nu)push_opnd(op,=)!(*ps=)&(get_opnd(op)=)change_opnd(*ps)=-1change_opnd(*ps)=-1strncpy(str3,ps,1)； strcat(str2,str3)； ps+push_num(nu,change_num(str2)strcpy(str2,)YY输出栈，显示栈的变化NYNYYYi+五、调试分析与设计体会a测试数据首先对程

22、序主导函数start（ ）进行测试，运行程序，得到界面如下情况：（图一）输入表达式，程序对输入的数据进行判断：（1）根据本程序的要求第一个字符只能是数字或“（”，最后一个字符只能是“=”；表达式括号必须配对，中间不能出现“=”；在“（”前面只能是“+、*、/、( ”，在“+、*、/、=、)”前面只能是数字或“）”；输入几组表达式如下情况：A组：测试输入：1+2=、2-1=、3*3=、6/3=；测试目的：两个单位数的四则运算；正确输出：3、1、9、2；实际输出：3、1、9、2；（图二）（图三）（图四）（图五）当前状态：通过；B组：测试输入：（56-20）/6=；测试目的：多个两位数括号的混合四则

23、运算；正确输出：6；（图六）实际输出：6；当前状态：通过；C组：测试输入：(8-2*3-6*2)/5=；测试目的：多个三位数括号的混合四则运算；正确输出：-2；（图七）接下图实际输出：-2；当前状态：通过；D组：测试输入：8=9=；（-8）+9=；测试目的：判别表达式的正确性。（图八）（图九）当前状态：通过；b.程序调试中遇到的问题以及解决问题的方法1.在对程序进行运行时，出现了运算符，操作数出进栈的错误。主要原因是在运算符优先级比较上出现错误。所以，列出表格并在编译器上进行调试，一步一步观察各个栈的变化情况。 + * / ( ) = + * / （ = =2.程序编写时出现的一些简单性的错误

24、，例如少分号，少括号等，这些只要点击编译器里面错误提示区，基本上能解决问题。c.课程设计过程经验教训、心得体会一个优秀程序员，需要有好的算法，好的效率，从这次课设，我发现我还差得很远，在学习和实践中，不能做到融会贯通，把以前的C语言只是当成敲门砖，这次在课设时，要我了解C语言和栈的完美实现。当然，这次程序的一些编程思想还是从树上借鉴的，所以更让我体会到吃透书本的重要性，当然基础是不能忘掉的。做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了

25、。我相信每件事有个总体规划，之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试。一口气写完程序的做法是不符合实际，这样只会徒增你花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做项目是这样，过我们的生活更是应该这样。感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可啊。通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。六、使用说明本程序在使用界面上人性化，尽量做到美观化进入使用界

26、面时，系统提醒你“请用户及时保存计算结果以便查看，每次回到主菜单时，若没有保存结果，则当次计算结果会被清除”，然后进入主菜单，选择你要执行的操作，刚开始可以选择计算式子，从键盘输入“y”或“Y”；接着输入要求的正确表达式，输出结果后，可以选择结束计算，这是按任意键即可结束结束。这是进入第二个主界面，我们可以对刚才的计算进行保存，这是键入“s”或“S”。然后可以方便我们进行查找本次计算似的数据，在进行查找时我们需要键入“r”或“R”。在进行多个表达式计算并成功保存后，我们可以进行所有数据的查询，这是你只需键入“l”或“L”。下面通过演示您可以更加直观了解本程序使用方法：A：进入第一主界面，键入“

27、y”后 （图一）主界面图B：根据提示输入正确表达式4+6= （图二）C：然后键入任意键推出计算，进入第二主界面（图三）D:选择键入“s”对计算结果进行保存E:键入“r”，可以对本次的计算结果进行查询（图四）六、附录源程序代码#include #include #include #include #define MAXSIZE 100#define N 1000int i=0;/*表达式数*/struct expression/*表达式结构*/long double result;char expstrMAXSIZE;exprN;typedef struct/*运算符栈的定义*/char cod

28、eMAXSIZE;int top;opnd;typedef struct/*数字栈定义*/double dataMAXSIZE;int top;num;/*-opnd栈操作-：*/void initstack(opnd *op)op-top=-1;int empty_opnd(opnd *op)if(op-top=-1)return 0;else return 1;int push_opnd(opnd *op,char co)if(op-top=MAXSIZE-1)printf(The opnd stack is full.);return 0;op-top+;op-codeop-top=co

29、;return 1;char pop_opnd(opnd *op)char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;a=op-codeop-top;op-top-;return a;char get_opnd(opnd *op)char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;elsereturn op-codeop-top;char Disp_opnd(opnd *op)int i;if(op-top=-1)pri

30、ntf(运算符栈为空!n);return 0;for(i=op-top;i=0;i-)printf(%c ,op-codei);return 1;/*-num栈操作-：*/void initstack(num *nu)nu-top=-1;int empty_num(num *nu)if(nu-top=-1)return 0;else return 1;int push_num(num *nu,double da)if(nu-top=MAXSIZE-1)printf(error:The data stack is full.);return 0;nu-top+;nu-datanu-top=da;

31、return 1;double pop_num(num *nu)double a=0;if(nu-top=-1)printf(error:The data stack is empty.);return a;a=nu-datanu-top;nu-top-;return a;double get_num(num *nu)if(nu-top!=-1)return nu-datanu-top;double Disp_num(num *nu)int i;if(nu-top=-1)printf(数字栈为空!n);return 0;for(i=nu-top;i=0;i-)printf(%f ,nu-dat

32、ai);return 1;/*-结束栈定义操作-*/*-函数操作-：*/int change_opnd(char code)/*将字符型操作码转换成优先级，非表达式字符反回-2*/switch(code)case =:return 1;break;case ):return 2;break;case +:return 3;break;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:

33、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)/（入栈return ();elseif(change_opnd(code)=2&change_opnd(top)=0)/（和）同时出现，（出栈，）不入栈return (=);elseif(change_opnd(code);elsereturn ();/入栈double cha

34、nge_num(char str)/数字字符串转成double型数字char *s=str;int p=1,q=0;/p=小数点前位数，q=小数点后位数char d=.,z=0;double da=0;if(strstr(str,d)=0)/判断是否有小数点p=strlen(str);elseif(strstr(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(int i=0;ip;i+)/小数点前的各位数乘

35、以各自的阶数，然后叠加：123=1*100+2*10+3*1da=da+(int)stri-48)*pow(10,p-i-1);for(int j=0;j0)/printf(n表达式只能以数字或(开头。请重新输入：);gets(expri.expstr);p=expri.expstr;n=0;continue;elseif(change_opnd(*p)=-2)printf(n表达式%c为非法字符。请重新输入：,*p);gets(expri.expstr);p=expri.expstr;n=0;continue;else/合法刚跳到下一个字符p=p+1;continue;if(change_o

36、pnd(*p)=-2)/非法字符判断printf(n表达式%c为非法字符。请重新输入：,*p);gets(expri.expstr);p=expri.expstr;n=0;continue;if(change_opnd(*p)=0)/(前一个字符只能是+、-、*、/、(if(change_opnd(*(p-1)4)if(change_opnd(*(p-1)!=0)printf(n表达式%c或%c不符合语法。请重新输入：,*(p-1),*p);gets(expri.expstr);p=expri.expstr;n=0;continue;if(change_opnd(*p)0)/+、-、*、/、=

37、、)前一个字符只能是数字和)if(change_opnd(*(p-1)!=-1)if(change_opnd(*(p-1)!=2)printf(n表达式%c或%c不符合语法。请重新输入：,*(p-1),*p);gets(expri.expstr);p=expri.expstr;n=0;continue;if(change_opnd(*p)=1)/判断表达式中是否有=重复出现，最后括号是否配对if(*(p+1)!=0)printf(n表达式中=，只能出现在表达式结束处。请重新输入：);gets(expri.expstr);p=expri.expstr;n=0;continue;if(n!=0)p

38、rintf(n表达式括号不配。请重新输入：);gets(expri.expstr);p=expri.expstr;n=0;continue;p=p+1;return 1;double caculate(opnd *op,num *nu)/简单计算+，-，*，/double b=pop_num(nu),a=pop_num(nu);switch(pop_opnd(op)case +:return(a+b);break;case -:return(a-b);break;case *:return(a*b);break;case /:return(a/b);break;void result(opnd

39、 *op,num *nu)/计算结果i=0;char str2MAXSIZE=,str32=0;char *ps=expri.expstr;initstack(op);/初始化栈initstack(nu);push_opnd(op,=);while(!(*ps=)&(get_opnd(op)=)/检查是表达式和操作码是否到尾if(change_opnd(*ps)=-1)/操作数处理while(change_opnd(*ps)=-1)strncpy(str3,ps,1);/数字字符一个个取出放在str2strcat(str2,str3);ps+;push_num(nu,change_num(str2);strcpy(str2,);else /操作码处理switch(procede(get_opnd(op),*ps)case :push_num(nu,caculate(op,nu); printf(nn 运算符栈为：n); /输出栈，显示栈的变化 Disp_opnd(op); printf(n 运算数栈为：n); Disp_num(nu);continue;break;if(*ps=)&get_opnd(op)=)ps+;continue;