安徽理工大学
数据结构
课程设计说明书题目: 表达式求值
院系:计算机科学与工程学院
专业班级:计算机12-1班
学号: 2012303038
学生姓名:丰继强
指导教师:刘文娟
2013年 12 月 25 日
安徽理工大学课程设计(论文)任务书
计算机科学与工程学院
2013年 11 月 21 日
安徽理工大学课程设计(论文)成绩评定表
目录
1 需求分析............................................... I
2 概要设计............................................... I
2.1 设计思路.......................................... I
2.2 存储结构设计..................................... II
2.3 功能模块设计..................................... II
3 详细设计.............................................. IV
4 运行与测试............................................ XI 5总结 ................................................. XII 参考文献.............................................. XIII
(要求:给出一级目录和二级目录,宋体,四号字,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
#include
#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
(要求:五号字,宋体,单倍行距。按作者.书名.地点: