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

往链点点通www.WL566.com 往链点点通www.WL566.com 往链点点通www.WL566.com 往链点点通共享资源，了解更多请登录www.WL566.com 北京理工大学珠海学院 《数据结构》课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 报告 题目：____________算术表达式求值_________________ 所在学院： 专业班级： 学生姓名： 指导教师： 2010年 05 月 26 日 目录 11．前 言 12．概要设计 12.1 数据结构设计 12.2 算法设计 22.3 ADT描述 22.4 功能模块分析 33．详细设计 33.1 数据存储结构设计 33.2主要算法流程图（或算法伪代码） 64．软件测试 85．心得体会 8参考文献 8附 录 1．前 言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT描述 ADT Stack{ 数据对象：D={ | ∈ElemSet,i=1,2,…，n, n≧0} 数据对象：R1={< >| , ,i=2,…，n} 约定 端为栈顶， 端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素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 Stack 2.4 功能模块分析 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的栈顶元素。 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函数把int型转换成字符串型，strlen函数可求字符长度。 (5) EvalExpr()主要操作函数运算功能。分析详细见“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. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。 算符间的优先关系如下： + - * / ( ) # + > < < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < = 表 1 算法伪代码如下： char Precede(char c1,char c2) { static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '='}; //用一维数组存储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 ')' : 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 (array[7*i+j]); /* 返回运算符array[7*i+j]为对应的c1,c2优先关系*/ } 2. int EvalExpr()主要操作函数。算法概要流程图： 利用该算法对算术表达式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 #*( 3 7-2)# Push(OPND,’7’) 5 #*( 3 7 -2)# Push(OPNR,’-’) 6 #*(- 3 7 2)# 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()//主要操作函数 { 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 '<': //栈顶元素优先权底 Push(&OPTR,c); c = *ptr++; break; case '=': //脱括号并接收下一字符 x=Pop(&OPTR); c = *ptr++; break; case '>'://退栈并将运算结果入栈 theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b)); break; } } 4．软件测试 1.运行成功后界面。 2.输入正确的表达式后。 3.更改表达式，输入有2位数的整数调试。 5．心得体会 这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构。课设题目 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。 这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写EvalExpr()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。 程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。 这个程序是我们3个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致导致整项工作的失败。实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败。团结协作是我们成功的一项非常重要的保证。而这次课程设计也正好锻炼我们这一点，这也是非常宝贵的 最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。 参考文献： 1.《数据结构(C语言版)》 严蔚敏 清华大学出版社 2.《C语言程序设计》 丁峻岭 中国铁道出版社 3.《C程序设计》 谭浩强 清华大学出版社 附 录 程序源代码： #include #include #include #define NULL 0 #define OK 1 #define ERROR -1 #define STACK_INIT_SIZE 100 #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 expr[255] = ""; /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *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; } 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 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->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; static char array[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 ')' : 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 (array[7*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 p[10]; itoa(n,p,10);//把整型转换成字符串型 n=strlen(p); return n; } int EvalExpr()//主要操作函数 { char c,theta,x; int n,m; int 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(&OPND,m); ptr=ptr+n; c=*ptr++; } else switch(Precede(GetTop(OPTR),c)) { case '<': Push(&OPTR,c); c = *ptr++; break; case '=': x=Pop(&OPTR); c = *ptr++; break; case '>': theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b)); break; } } return GetTop2(OPND); } int main( ) { printf("请输入正确的表达式以'#'结尾:"); do{ gets(expr); }while(!*expr); InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,'#'); /* 将#压入运算符栈 */ InitStack2(&OPND); /* 初始化操作数栈 */ printf("表达式结果为:%d\n", EvalExpr()); return 0; } 课程设计成绩评定表 教师 评语 评语下载剧本评语下载小学第一学期期末评语免费下载小学一年级学生评语考生思想政治品德考核评语 1、课程设计表现： 2、程序、软件质量： 3、设计报告质量： 4、答辩表现： 5、独到的见解、方法与创新性： 6、总结： 成绩记录 平时成绩（10分） 程序检查（20+20分） 设计报告文档（20分） 课程设计答辩（20+10分） 最后（百分）成绩 成绩（等级）评定 往链点点通共享资源 ----------------------------- 资料说明 ----------------------------- 该资源由往链点点通搜索于网络公开资源，仅供网友浏览阅读，请勿用于商业用途； 往链点点通，是免费的新一代电脑管理、网络应用桌面软件。 通过简洁清爽并可随意切换的两种窗口操作界面，构建了用户、电脑、互联网之间顺畅的入口平台。为用户管理电脑、智能办公、快捷上网、玩转应用（如 游戏，），提供全方位一站式的服务。让用户只需通过往链点点通，就能便捷到达信息时代的各个角落。真正实现一键直达，点点就通。 往链快搜索：无论是搜索硬盘资源、查找网络资源，还是追踪热门应用，都能享受前所未所的快速度。如本地文件搜索，千万文件，零秒呈现；如网络搜索，只需输入一次关键词，便能同步打开百度、google等多个搜索引擎的结果页； 往链优应用：与某些软件相比，往链点点通追求绿色无广告的体验，精选最优质的网络应用，为用户提供纯净实在的生活、工作、学习、娱乐、休闲应用空间。 往链点点通，让您用windows的使用习惯享受苹果的操作体验！ 查看和分享更多优质资源，请进入www.WL566.com 下载往链点点通，找到您的一切网络所需！ 往链网址导航大全 www.www321.com 往链点点通，让您无障碍畅游网络世界！ 往链点点通www.WL566.com 往链点点通www.WL566.com 往链点点通www.WL566.com _1336667776.unknown _1336667819.unknown _1336667934.unknown _1336667979.unknown _1336667840.unknown _1336667801.unknown _1336667685.unknown