数据结构课程设计算术表达式求值的实现

《数据结构课程设计算术表达式求值的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计算术表达式求值的实现（16页珍藏版）》请在装配图网上搜索。

1、课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计课程设计题目：算术表达式求值的实现院（系）：*专 业：*班 级：*学 号：*姓 名：*指导教师：*沈阳航空航天大学课程设计报告 I 目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容.11.2 课程设计要求.12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析.22.2 原理图介绍.22.2.1 功能模块图.22.2.2 流程图分析.33 数据结构分析数据结构分析.53.1 存储结构.53.2 算法描述.54 4 调试与分析调试与分析.74.1 调试过程.74.2 程序执行过程.7参考文献参考文献.8附附

2、 录（关键部分程序清单）录（关键部分程序清单）.9沈阳航空航天大学课程设计报告 1 1 1 课程设计介绍课程设计介绍1.11.1 课程设计内容课程设计内容 编写算法能够进行整型和实型数的表达式求值，能够根据运算的数据选择正确的运算结果的数据类型，表达式的运算符为：+，*，/， （， ） ，且括号可以嵌套。1.21.2 课程设计要求课程设计要求 1.给出必要的输入、输出信息和提示信息。 2.参考相应的资料，独立完成课程设计任务。 3.交规范课程设计报告和软件代码。沈阳航空航天大学课程设计报告 2 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，

3、拟将整体程序分为三大模块。此三个模块相互独立，没有嵌套调用的情况，以下是三个模块的大体分析： 1.首先依次定义字符类型栈、整型栈、运算符栈和操作数栈，构造运算符栈和操作数栈，然后运算符、操作数依次入栈。 2. 依次读入表达式，若是操作符即进 OPND 栈，若是运算符即进 OPTR 栈。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即 top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针 top 增 1，删除栈顶元素时，指针 top 减 1。 3. 按照运算

4、符的优先级别对表达式进行求值运算。2.22.2 原理图介绍原理图介绍 该功能模块图介绍了这个程序的主要功能。2.2.12.2.1 功能模块图功能模块图算术表达式求值存储 读取 计算操作数入栈操作符入栈 操作数出栈操作数出栈字符转换成浮点数+- */ 计算图 2.1 功能模块图沈阳航空航天大学课程设计报告 3 如图 2.1 所示, 要实现表达式的求值，即必须要实现存储、读取和计算三项功能。存储即运算符、操作数的入栈；读取即运算符、操作数的出栈；计算即+、*、/的运算。2.2.22.2.2 流程图分析流程图分析 1Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。

5、算符间的优先关系如下：表 2.1 运算符优先关系列表+-*/()#+-*/(#= 2int EvalExpr()主要操作函数。算法概要流程图：开始Char c=表达是首字符NC!=#|GetTop(OPTR)!=#!In(c)进操作数栈c=*ptr+returnGetTop(OPND)结束YCase:操作数栈头2个数进行运算图 2.2 主要操作函数流程图沈阳航空航天大学课程设计报告 4 3.入栈出栈主要流程。开始运算符栈插入ch为新的栈顶元素操作数栈插入ch为新的栈顶元素删除运算符栈s的栈顶元素，用p返回其值删除操作数栈s的栈顶元素，用p返回其值用p返回运算符栈s的栈顶元素用p返回运算符栈s的

6、栈顶元素结束图 2.3 入栈出栈主要流程图沈阳航空航天大学课程设计报告 5 3 数据结构分析数据结构分析3.13.1 存储结构存储结构因为表达式是由操作符，运算符和界限符组成的。如果只用一个 char 类型栈，不能满足 2 位以上的整数，所以还需要定义一个 int 类型的栈用来寄存操作数。/* 定义字符类型栈 */typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;3.23.2 算法描述算法

7、描述 1.栈的基本功能。InitStack(Stack *s) 和 InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(Stack *s,char ch) 运算符栈插入 ch 为新的栈顶元素，Push2(Stack2 *s,int ch) 操作数栈插入 ch 为新的栈顶元素，Pop(Stack *s) 删除运算符栈 s 的栈顶元素，用 p 返回其值，Pop2(Stack2 *s)删除操作数栈 s的栈顶元素，用 p 返回其值，GetTop(Stack s)用 p 返回运算符栈 s 的栈顶元素，GetTop2(Stack2 s) 用 p 返回操作数栈 s 的栈顶元素

8、。 2.其它功能分析。沈阳航空航天大学课程设计报告 6 (1)In(char ch) 判断字符是否是运算符功能，如果该字符是运算符返回 1，实现该功能的算法 return(ch=+|ch=-|ch =*|ch=/|ch= (|ch =)|ch=#)。 (2) Precede(char c1,char c2) 判断运算符优先权功能，该函数判断运算符 c1,c2的优先权，具体优先关系参照表 1。 (3) Operate(int a,char op,int b)操作数用对应的运算符进行运算功能。运算结果直接返回。 (4) num(int n) 求操作数的长度功能，需要用 itoa 函数把 int 型

9、转换成字符串型，strlen 函数可求字符长度。 (5) EvalExpr()主要操作函数运算功能。沈阳航空航天大学课程设计报告 7 4 4 调试与分析调试与分析4.14.1 调试过程调试过程 在调试程序是主要遇到一下几类问题：1.在括号，分号，引号，或者数据类型上总发生错误。2.在写 EvalExpr()函数时，忘了指针的地址符值不用加*号。3.运行程序时由于忘记更改中英文输入法，导致输入中文（） ，程序无法正cha 常执行。4.程序开始编写时我仅仅编写了整型数的计算，通过修改后改成浮点类型的运算，使程序可操作性更强。4.2 程序执行过程程序执行过程1.请输入正确的表达式以#结尾：4*（7-

10、2）# 表达式结果为：20.000000 Press any key to continue 2.请输入正确的表达式以#结尾：11+123*4# 表达式结果为：503.000000 Press any key to continue 3.请输入正确的表达式以#结尾：4.2*(5+1.2)# 表达式结果为：26.040000 Press any key to continue 4.请输入正确的表达式以#结尾：42.6/(3.2+2.8)# 表达式结果为：7.100000 Press any key to continue 沈阳航空航天大学课程设计报告 8 参考文献参考文献1 严蔚敏，吴伟民. .

11、数据结构M.北京：清华大学出版社，2007.2 张长海，陈娟. .C 程序设计M.北京：高等教育出版社，2004. 3 谭浩强. .C 程序设计M.北京：清华大学出版社，2005. .4 丁峻岭.C 语言程序设计M.北京：中国铁道出版社，2006.5 徐孝凯.数据结构实用教程M.清华大学出版社，2006. 沈阳航空航天大学课程设计报告 9 附附 录（关键部分程序清单）录（关键部分程序清单）程序代码程序代码#include #include #include #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 1

12、00#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; float *base; float *top; Stack2;/* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/Stack2 OPND; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int InitStack(S

13、tack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE;return OK; 沈阳航空航天大学课程设计报告 10 int InitStack2(Stack2 *s) /构造操作数栈 s-base=(float *)malloc(STACK_INIT_SIZE*sizeof(float); if(!s-base) return ERROR; s-stacksize=STACK_IN

14、IT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回 1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) /运算符栈插入 ch 为新的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,float ch)/操作数栈插入 ch 为新的栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈 s 的栈顶元

15、素，用 p 返回其值 char p;s-top-; p=*s-top; return p; float Pop2(Stack2 *s)/删除操作数栈 s 的栈顶元素，用 p 返回其值 float p;s-top-; p=*s-top; return p;char GetTop(Stack s)/用 p 返回运算符栈 s 的栈顶元素 char p=*(s.top-1); return p; 沈阳航空航天大学课程设计报告 11 float GetTop2(Stack2 s) /用 p 返回操作数栈 s 的栈顶元素 float p=*(s.top-1); return p; /* 判断运算符优先权，

16、返回优先权高的 */ char Precede(char c1,char c2) int i=0,j=0; static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1) /* i 为下面 array 的横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case )

17、 : i=5;break; case # : i=6;break; switch(c2) /* j 为下面 array 的纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符 */ 沈阳航空航天大学课程设计报告 12 /*操作函数 */ float Operate(float a,char op,fl

18、oat b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); return 0; int num(float n)/返回操作数的长度 char p10;int pl;itoa(int)n,p,10);/把整型转换成字符串型pl=2*strlen(p);return pl;float EvalExpr()/主要操作函数 char c,theta,x; int n;float m;float a,b; c = *ptr+; while(c!=

19、#|GetTop(OPTR)!=#) if(!In(c) if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case : theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; return GetTop2(OPND); int main( ) printf(请输入正确的表

20、达式以#结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,#); /* 将#压入运算符栈 */ InitStack2(&OPND); /* 初始化操作数栈 */ printf(表达式结果为:%fn, EvalExpr();getchar();return 0; 课程设计总结：课程设计总结：这次课程设计让我更加了解大一学到的 C 和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一

21、个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写 EvalExpr()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。 程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到 C 语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩