当前位置:文档之家› 数据结构(C语言版)课程设计报告表达式求值

数据结构(C语言版)课程设计报告表达式求值

安徽理工大学

数据结构

课程设计说明书题目: 表达式求值

院系:计算机科学与工程学院

专业班级:计算机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

(要求:五号字,宋体,单倍行距。按作者.书名.地点:

相关主题
相关文档 最新文档