数据结构（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>=48&&c<=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>=40&&c<=43)||c==45||(c>=47&&c<=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(“ =%f＼n“,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 (要求:五号字，宋体，单倍行距。按作者.书名.地点：
