数据结构（C语言版）课程设计报告表达式求值说明书.docx

数据结构（C语言版）课程设计报告表达式求值说明书 XX高校 数据结构 课程设计说明书 题目: 表达式求值 院 系： 计算机科学与工程学院 专业班级： 计算机班 学 号： 学生姓名： 指导老师： 2013年 X 月X 日 XX高校课程设计（论文）任务书 计算机科学与工程 学院 学 号 学生姓名 专业（班级） 设计题目 表达式求值 设 计 技 术 参 数 系统平台：Windows 7/Windows XP 开发工具：VC+6.0 设 计 要 求 （1）能够计算的运算符包括：加、减、乘、除、圆括号。 （2）能够计算的数要求在实数范围内。（3）能执行多重括号嵌套运算。（4）对于异样表达式给出错误提示。工 作 量 课程设计报告要求不少于3000字。源程序要求不少于300行 工 作 计 划 2013.11.21-12.01 依据课程设计大纲的要求，查找相关资料，完成需求分析； 2013.12.02-12.16 进行系统的概要设计； 2013.12.17-12.31 进行系统的具体设计和源代码的书写； 2014.01.01-01.17 对系统进行调试分析，写出课程设计报告。参 考 资 料 1何钦铭主编.C语言程序设计.北京：高等教化出版社,2007. 2谭浩强编著.C程序设计（第四版）.北京：清华高校出版社,2008. 3严蔚敏,吴伟民编著.数据结构（C语言版）北京：清华高校出版社,2007. 4严蔚敏,吴伟民编著.数据结构题集 北京：清华高校出版社,2007. 指导老师签字 教研室主任签字 2013年 X月 X 日 学生姓名： 学号： 专业班级： 课程设计题目： 表达式求值 指导老师评语： 成果： 指导老师： 年 月 日 XX高校课程设计（论文）成果评定表 目录 1 需求分析 1 2 概要设计 1 2.1 设计思路 1 2.2 存储结构设计 1 2.3 功能模块设计 1 3 具体设计 1 4 运行与测试 1 5总结 1 参考文献 2 (要求：给出一级书目和二级书目，宋体，四号字,1.5倍行距，页码运用罗马数字，居中) （报告正文部分）： (要求：正文部分一律用小四号字，宋体，行距20磅。一级标题靠左，加粗。二级大标题靠左，不加粗。正文页码单独起先用阿拉伯数字编码，居中) 1 需求分析 1、程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理小数，推断表达式是还语法正确，正的确现对算术四则混合运算表达式的求值。  2、输入的形式和输入值的范围：以字符串的形式输入表达式，以“#”结束。  3、输出的形式：在计算过程中遇到的问题或最终的答案将显示在屏幕上。  4、测试数据：输入“3*(7-2)#”时，输出“15.000000”，测试正确；输入“!(9-2)#”时，输出“输入错误!”，测试正确。2 概要设计 2.1 设计思路 为了实现算符优先算法，可以运用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是： （1）首先置非运算符栈为空栈，表达式起始符“#” 为运算符栈的栈底元素； （2）依次读入表达式中每个字符，若是非运算符则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。算法中还调用了两个函数，其中Precede是判定运算符栈顶运算符a与读入的运算符b之间优先关系的函数；Operate为进行二元运算a theta b的函数，假如是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；假如是说明执行表达式，则干脆进行该运算，并返回运算结果。 2.2 存储结构设计  因为表达式是由操作符，运算符和界限符组成的。所以须要两个栈，一个char类型栈用来寄存运算符，一个int类型的栈用来寄存非运算符。  /定义结点元素结构（用于存放运算符） typedef struct charstack char *base; char *top; int stacksize; SqStackchar; /定义结点元素结构（用于存放非运算符） typedef struct intstack float *base; float *top; int stacksize; SqStackint; 2.3 功能模块设计 1.栈的基本功能： (1) InitStackchar(Stackchar S)：构造运算符栈 (2) InitStackint(Stackint S)：构造非运算符栈 (3) Pushchar(SqStackchar S，char e)：运算符栈插入元素e为新的栈顶元素 (4) Pushint(SqStackint S，float e)：非运算符栈插入元素e为新的栈顶元素 (5) Popchar(SqStackchar S，char e)： 删除运算符栈S的栈顶元素，用e返回其值 (6) Popint(SqStackint S，float e)：删除非运算符栈S的栈顶元素，用e返回其值 (7) GetTopchar(SqStackchar S)：用e返回运算符栈S的栈顶元素 (8) float GetTopint(SqStackint S): 用e返回操作数栈S的栈顶元素 2.其它功能分析： (1) Xiaoshu(char c)用于计算小数。 (2) Precede(char a，char b) 推断运算符优先权功能，算符间的优先关系见表1： 表1 算符间的优先关系 + - * / ( ) # + > < < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < = (3) Operate(float a，char theta，float b) 操作数用对应的运算符进行运算功能，运算结果干脆返回。  3 具体设计(程序源代码) #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 /存储空间初始安排量 #define STACKINCREMENT 10 /存储空间安排增量 typedef struct charstack char *base; /在栈构造之前，base的值为NULL char *top; /栈顶指针 int stacksize; /当前已安排的存储空间，以元素为单位 SqStackchar; /定义结点元素结构（用于存放运算符） typedef struct intstack float *base; /在栈构造之前，base的值为NULL float *top; /栈顶指针 int stacksize; /当前已安排的存储空间，以元素为单位 SqStackint; /定义结点元素结构（用于存放非运算符） int InitStackchar(SqStackchar S) /构造一个空栈（用于存放非运算符） S.base=(char *)malloc(MAXSIZE * sizeof(char); if(!S.base) return 0; /存储安排失败 S.top=S.base; /空栈 S.stacksize=MAXSIZE; return 1; int InitStackint(SqStackint S) /构造一个空栈（用于存放运算符） S.base=(float *)malloc(MAXSIZE * sizeof(float); if(!S.base) return 0; /存储安排失败 S.top=S.base; /空栈 S.stacksize=MAXSIZE; return 1; int Pushchar(SqStackchar S,char e) /元素进运算符的栈 if(S.top-S.base>=S.stacksize) /栈满，追加存储空间 S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) return 0; /存储安排失败 S.top=S.base+S.stacksize; /因为s.base可能不是原来值 S.stacksize+=STACKINCREMENT; *S.top+=e; /元素入栈，栈顶指针增1 return 1; int Pushint(SqStackint S,float e) /元素进非运算符的栈 if(S.top-S.base>=S.stacksize) /栈满，追加存储空间 S.base=(float *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(float); if(!S.base) return 0; /存储安排失败 S.top=S.base+S.stacksize; /因为s.base可能不是原来值 S.stacksize+=STACKINCREMENT; *S.top+=e; /元素入栈，栈顶指针增1 return 1; char GetTopchar(SqStackchar S) /取栈顶元素（存放运算符的栈顶元素） char e; if(S.top=S.base) return 0; e=*(S.top-1); /栈本身不变更 return e; float GetTopint(SqStackint S) /取栈顶元素（存放非运算符的栈顶元素） float e; if(S.top=S.base) return 0; e=*(S.top-1); /栈本身不变更 return e; int Xiaoshu(char c) if(c>=48c<=57) c-=48; return c; else return 0; int Popchar(SqStackchar S,char e) /出栈（运算符） if(S.top=S.base) return 0; e=*-S.top; /栈顶指针减1，并取出当前指向元素 return 1; int Popint(SqStackint S,float e) /出栈（非运算符） if(S.top=S.base) return 0; e=*-S.top; /栈顶指针减1，并取出当前指向元素 return 1; char Precede(char a,char b) /推断运算符栈的栈顶元素与读入的运算符之间优先关系的函数 char c; if(a=+|a=-) if(b=*|b=/|b=() return c=< else return c=> else if(a=*|a=/) if(b=() return c=< else return c=> else if(a=() if(b=) return c=; else if(b=#) printf(“ “); exit(0); else return c=< else if(a=) if(b=() printf(“ “); exit(0); else return c=> else if(a=#) if(b=#) return c=; else if(b=) printf(“ “); exit(0); else return c=< float Operate(float a,char theta,float b) /执行相应的运算操作 float c; switch(theta) case +:c=a+b; break; case -:c=a-b; break; case *:c=a*b; break; case /:if(b!=0)c=a/b; else printf(“输入错误!n“); break; return c; void main() SqStackchar OPTR; SqStackint OPND; float a,b; int sum=0; int m=1; float f; char c,x,theta; InitStackchar(OPTR); Pushchar(OPTR,#); InitStackint(OPND); printf(“n“); printf(“*学号：2012303038*n“); printf(“n“); printf(“*课程设计：表达式求值*n“); printf(“n“); printf(“请输入表达式并以#结尾:n“); c=getchar(); if(c=35|(c>=40c<=43)|c=45|(c>=47c<=57) while(c!=#|GetTopchar(OPTR)!=#) if(Xiaoshu(c) sum=sum*10+Xiaoshu(c); c=getchar(); while(Xiaoshu(c)|c=.) if(c=.) c=getchar(); while(Xiaoshu(c) m*=10; sum=sum*10+Xiaoshu(c); c=getchar(); else sum=sum*10+Xiaoshu(c); c=getchar(); f=sum/(float)m; Pushint(OPND,f); sum=0; m=1; /不是运算符就进栈 else switch(Precede(GetTopchar(OPTR),c) case <: /栈顶元素优先权低 Pushchar(OPTR,c); c=getchar(); break; case =: /拖脱括号并接受下一个字符 Popchar(OPTR,x); c=getchar(); break; case >: /退栈并将运算结果进栈 Popchar(OPTR,theta); Popint(OPND,b); Popint(OPND,a); Pushint(OPND,Operate(a,theta,b); break; printf(“ =%fn“,GetTopint(OPND); else printf(“输入错误!n“); 4 运行与测试 1加法测试，输入正确，输出正确，测试正确： 2减法测试，输入正确，输出正确，测试正确： 3乘法测试，输入正确，输出正确，测试正确： 3除法测试，输入正确，输出正确，测试正确： 4输入表达式正确，输出正确，测试正确： 5输入表达式错误，能正确推断，测试正确： 5总结 通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及C语言的运用都有了更深的了解。当然也遇到不少问题，也正是国为这些问题引发的思索给我带来了收获。从当时不喜爱上机写程序到现在能主动写程序，从当时拿着程序不知从何下手到现在知道如何分析问题，如何用专业学问解决实际问题的转变。我发觉无论是专业学问还是动手实力，自己都有很大程度的提高。在事实上机操作过程中，不仅是让我们了解数据结构的理论学问，更重要的是培育解决实际问题的实力，为后续课程的学习及实践打下良好的基础。这次课程设计让我更加了解大一学到的C语言和这个学期学到的数据结构的紧密联系。设计题目不仅要求设计者对课本学问有较深刻的了解，同时要有较强的思维动手实力。  这次的课程设计让我有一个深刻的体会：严谨！编程最须要的就是严谨，往往检查到的错误是在某个括号、分号、引号等不应当犯错的地方上。程序设计时难免遇到错误，但这不是坏事情，它可以让我发觉自己的薄弱环节，在详细操作中还可以巩固所学的C语言及数据结构。更加体会到了C语言的语句简洁、运用敏捷、执行效率高等特点。另外留意：报告中图表格式要求如下 （1）正文中图表要规范，图号、图题在图下方正中，五号字，表号、表题在表格上方正中，五号字。图的编号从图1起先，表的编号从表1起先。（2）表格内的文字用宋体，五号字，不加粗。（3）正文中应有对图表的引用，图的引用为：“如图*所示”，表的引用为：“见表*”。如： 图： 图1 图题 表： 表1 表题 内容 字体 段落 行间距 字间距 表格文字 宋体五号 居中 1倍 标准 参考文献 1 刘国钧,陈绍业,王凤翥. 图书馆书目M. 北京：高等教化出版社，1957 (要求:五号字，宋体，单倍行距。按作者.书名.地点：