数据结构算术表达式求值实验报告

1、北京理工大学珠海学院北京理工大学珠海学院数据结构数据结构课程设计报告课程设计报告题目：题目：_算术表达式求值算术表达式求值_所在学院：所在学院：专业班级：专业班级：学生姓名：学生姓名：指导教师：指导教师：2010 年年 05 月月 26 日日目录目录1前前 言言12概要设计概要设计12.1 数据结构设计数据结构设计12.2 算法设计算法设计12.3 adt 描述描述22.4 功能模块分析功能模块分析23详细设计详细设计33.1 数据存储结构设计数据存储结构设计33.2 主要算法流程图（或算法伪代码）主要算法流程图（或算法伪代码）34软件测软件测试试65心得体会心得体会8参考文献参考文献8附附

2、录录81前前 言言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入） 。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。2概要设计概要设计2.1 数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺

3、序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即 top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针 top 增 1，删除栈顶元素时，指针 top 减 1。2.2 算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为 optr，用以寄存运算符，另一个称做opnd，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表

4、达式，若是操作符即进 opnd 栈，若是运算符则和 optr 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即 optr 栈的栈顶元素和当前读入的字符均为”#”） 。2.3 adt 描述adt stack数据对象：d= |elemset,i=1,2,，n, n0iaia数据对象：r1=|,i=2,，n1,iiaa1iadai约定端为栈顶，端为栈底。naia基本操作： initstack(&s) 操作结果：构造一个空栈 s。 gettop(s) 初始条件：栈 s 已存在。 操作结果：用 p 返回 s 的栈顶元素。 push(&s，ch) 初始条件：栈 s 已存在。 操作结果：插

5、入元素 ch 为新的栈顶元素。 pop(&s) 初始条件：栈 s 已存在。 操作结果：删除 s 的栈顶元素。in(ch)操作结果：判断字符是否是运算符，运算符即返回 1。 precede(c1, c2) 初始条件：c1,c2 为运算符。操作结果：判断运算符优先权，返回优先权高的。operate(a,op,b)初始条件：a,b 为整数，op 为运算符。操作结果：a 与 b 进行运算，op 为运算符，返回其值。num(n)操作结果：返回操作数的长度。evalexpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。adt stack2.4 功能模块分析1.栈的基本功能。initstac

6、k(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 的栈顶元素。2.其它功能分析。 (1)in(ch

7、ar 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 型转换成字符串型，strlen 函数可求字符长度。(5) evalexpr

8、()主要操作函数运算功能。分析详细见“3.详细设计3.2” 。3详细设计详细设计3.1 数据存储结构设计 因为表达式是由操作符，运算符和界限符组成的。如果只用一个 char 类型栈，不能满足 2 位以上的整数，所以还需要定义一个 int 类型的栈用来寄存操作数。/* 定义字符类型栈 */typedef struct int stacksize; char *base; char *top; stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; stack2;3.2 主要算法流程图（或算法伪代码）1. prece

9、de(char c1,char c2) 判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一维数组存储 49 种情况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

10、 ) : 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); /* 返回运算符 array7*i+j为对应的 c1,c2 优先关系*/ 2. int evalexpr()主要操作函数。算法概要流程图：利

11、用该算法对算术表达式 3*(7-2)求值操作过程如下：步骤optr 栈opnd 栈输入字符主要操作1#3*(7-2)#push(opnd,3)2#3*(7-2)#push(optr,*)3#*3(7-2)#push(opnr,()4#*(37-2)#push(opnd,7)5#*(3 7-2)#push(opnr,-)6#*(-3 72)#push(opnd,2)7#*(-3 7 2)#operate(7,-,2)8#*(3 5)#pop(optr)9#*3 5#operate(3,*,5)10#15#return(gettop2(opnd)表 2算法伪代码如下：int evalexpr()/

12、主要操作函数 c = *ptr+; while(c!=#|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;

13、4软件测试软件测试1.运行成功后界面。2.输入正确的表达式后。3.更改表达式，输入有 2 位数的整数调试。5心得体会心得体会这次课程设计让我更加了解大一学到的 c 和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写 evalexpr()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。 程序设计

14、时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到 c 语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。 这个程序是我们 3 个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致导致整项工作的失败。实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败。

15、团结协作是我们成功的一项非常重要的保证。而这次课程设计也正好锻炼我们这一点，这也是非常宝贵的最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。参考文献参考文献：1.数据结构(c 语言版) 严蔚敏 清华大学出版社 2.c 语言程序设计 丁峻岭 中国铁道出版社 3.c 程序设计 谭浩强 清华大学出版社附附 录录程序源代码：#include #include #include #define null 0 #define ok 1#define error -1 #define stack_init_size 100#

16、define stackincrement 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; stack2;/* - 全局变量- */ stack optr;/* 定义运算符栈*/stack2 opnd; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int initstack(stack *s

17、) /构造运算符栈 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; int initstack2(stack2 *s) /构造操作数栈 s-base=(int *)malloc(stack_init_size*sizeof(int); if(!s-base) return error; s-stacksize=stack_init_size; s-top=s-base; return

18、 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,int ch)/操作数栈插入 ch 为新的栈顶元素 *s-top=ch; s-top+; return 0; char pop(stack *s) /删除运算符栈 s 的栈顶元素，用 p 返回其值 char p;s-top-; p=*s-

19、top; return p; int pop2(stack2 *s)/删除操作数栈 s 的栈顶元素，用 p 返回其值 int p;s-top-; p=*s-top; return p;char gettop(stack s)/用 p 返回运算符栈 s 的栈顶元素 char p=*(s.top-1); return p; int gettop2(stack2 s) /用 p 返回操作数栈 s 的栈顶元素 int p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的 */ char precede(char c1,char c2) int i=0,j=0; sta

20、tic 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

21、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); /* 返回运算符 */ /*操作函数 */ int operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); return 0; int num(int n)/返回操作数的长度 char p10;itoa(n,p,10);/把整型转换成字符串型n=strlen(p);ret