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

1、课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计 课程设计题目：算术表达式求值的实现 院（系）：* 专 业：* 班 级：* 学 号：* 姓 名：* 指导教师：* 目目 录录 1 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容.1 1.2 课程设计要求.1 2 2 课程设计原理课程设计原理.2 2.1 课设题目粗略分析.2 2.2 原理图介绍.2 2.2.1 功能模块图.2 2.2.2 流程图分析.3 3 数据结构分析数据结构分析.5 3.1 存储结构.5 3.2 算法描述.5 4 4 调试与分析调试与分析.7 4.1 调试过程.7 4.2 程序执行过程.7 参考文献参

2、考文献.8 附附 录（关键部分程序清单）录（关键部分程序清单）.9 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 编写算法能够进行整型和实型数的表达式求值，能够根据运算的数据选 择正确的运算结果的数据类型，表达式的运算符为：+，*，/， （， ） ，且 括号可以嵌套。 1.21.2 课程设计要求课程设计要求 1.给出必要的输入、输出信息和提示信息。 2.参考相应的资料，独立完成课程设计任务。 3.交规范课程设计报告和软件代码。 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 功能模块图 如图 2.1 所示, 要实现表达式的求值，即必须要实现存储、读取和计算三项 功能。存储即运算符、操作数的入栈；读取即运算符、操作数的出栈；计算即 +、*、/的运算。 2.2.22.2.2 流程图分析流程图分析 1precede(char c1,char c2) 判断运算符优先权，返回优

5、先权高的。 算符间的优先关系如下： 表 2.1 运算符优先关系列表 +-*/()# + - * / ( #= 2int evalexpr()主要操作函数。算法概要流程图： 开始 char c=表达是首字符 n c!=#|gettop(optr)!=# !in(c) 进操作数栈c=*ptr+ returngettop(opnd) 结束 y case: 操作数栈头2个数进行运算 图 2.2 主要操作函数流程图 3.入栈出栈主要流程。 开始 运算符栈插入ch为新的栈顶元素 操作数栈插入ch为新的栈顶元素 删除运算符栈s的栈顶元素，用p返回其值 删除操作数栈s的栈顶元素，用p返回其值 用p返回运算符栈

6、s的栈顶元素 用p返回运算符栈s的栈顶元素 结束 图 2.3 入栈出栈主要流程图 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.

7、23.2 算法描述算法描述 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) 用

8、p 返回操作数栈 s 的栈顶元素。 2.其它功能分析。 (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 函数把 in

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

10、 表达式结果为：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 参考文献参考文献 1 严蔚敏，吴伟民. .数据结构m.北京：清华大学出版社，20

11、07. 2 张长海，陈娟. .c 程序设计m.北京：高等教育出版社，2004. 3 谭浩强. .c 程序设计m.北京：清华大学出版社，2005. . 4 丁峻岭.c 语言程序设计m.北京：中国铁道出版社，2006. 5 徐孝凯.数据结构实用教程m.清华大学出版社，2006. 附附 录（关键部分程序清单）录（关键部分程序清单） 程序代码程序代码 #include #include #include #define null 0 #define ok 1 #define error -1 #define stack_init_size 100 #define stackincrement 20 /

12、* 定义字符类型栈 */ 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(stack *s) /构造运算符栈 s-base=(c

13、har *)malloc(stack_init_size*sizeof(char); if(!s-base) return error; s-top=s-base; s-stacksize=stack_init_size; return ok; int initstack2(stack2 *s) /构造操作数栈 s-base=(float *)malloc(stack_init_size*sizeof(float); if(!s-base) return error; s-stacksize=stack_init_size; s-top=s-base; return ok; int in(ch

14、ar 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 的栈顶元素，用 p 返回其值 char p; s-top-; p=*s-top; return

15、 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; float gettop2(stack2 s) /用 p 返回操作数栈 s 的栈顶元素 float p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的 */ char precede(char c1,char c2) int i=0,j=0; stat

16、ic 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 ) : i=5;break; case # : i=6;break; switch(c2) /* j 为下面 arr

17、ay 的纵标 */ 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); /* 返回运算符 */ /*操作函数 */ float operate(float a,char op,float b) switch(op) case + : return (a+b); case - : return (a-b); case * : re

18、turn (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!=#|gettop(optr)!=#) if(!in(c) if(!in(*(ptr-1) ptr=ptr-1; m=atoi(ptr);/取字符串前面的数字段 n=num(m); push2( ptr=ptr+n; c=*ptr+; else switch(precede(gettop(optr),c) case : theta=pop( b=pop2( a=pop2( push2( break; return gettop2(opnd); int main( ) printf(请输入正确的表达式