表达式求值.doc

数据结构课程设计报告设计题目：表达式求值 年 级 05级 班 级 姓 名 学 号 指导教师 起止时间 2007.11.2611.30 2007 年第一学期一实习目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。三需求分析为实现算符优先算法,可以使用两个工作栈。一个称做OPTR，用以寄存运算符;另一个称做OPND;用以寄存操作数或运算结果。算法的基本思想是： 1) 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素; 2) 依次读入表达式中每个字符,若是操作数则OPND栈,若是运算符,则和OPTR栈的栈顶运算 符比较优先权后做相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为#)。 该程序实现表达式的求值问题：（1） 从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则混合运算的求值，输出正确的结果。（2） 显示输入序列和栈的变化过程。四概要设计 程序流程图: 开始优先级比较算法Operate 算法建立栈存放操作字符存放数据EvaluateExpression算法计算结束 系统用到的抽象数据类型定义：1ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S, &e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(&S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 StackEmpty(&s) 初始条件: 栈S已存在。 操作结果:若S为空栈，则返回TRUE, 否则返回FALSE Pop(&S, &e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 ADT Stack 系统中子程序及功能要求：1、F(char c) :函数实现的功能是把操作符转换成相应的数字，并返回其值。2、visitoptr(sqstack c): 函数实现的功能是对操作符栈进行遍历，并在屏 幕上输出遍历到的各操作符。3、visitopnd(sqstack c): 函数实现的功能是对操作符栈进行遍历，并在屏幕上输出遍历到的各操作数。4、printstep():函数实现打印程序执行的步骤在屏幕上输出。5、compare(char c1,char c2):通过原来的设定比较两个字符的优先级。6、operate(elmtype a,elmtype t,elmtype b):函数进行四则运算，并返回结果。7、EvaluateExpression()：函数对以上函数进行调用，实现表达式的求值并打印出计算过程，完成程序的总体功能，返回表达式的计算结果。 各程序模块之间的调用关系主函数可调用子程序7子程序5调用子程序1 子程序7可调用子程序1，2，3，4，5，6 五详细设计(C语言) 源程序/*表达式求值*/#include #include #include /判断是否为字符的函数的头文件#define MAXSIZE 100typedef int elmtype;typedef struct sqstack sqstack;/由于sqstack不是一个类型 而struct sqstack才是char ch7=+,-,*,/,(,),#;/把符号转换成一个字符数组int f17=3,3,5,5,1,6,0;/栈内元素优先级int f27=2,2,4,4,6,1,0;/栈外的元素优先级int n=0;struct sqstack elmtype stackMAXSIZE; int top;void Initstack(sqstack *s) s-top=0;bool StackEmpty(sqstack S ) /若S为空栈，则返回TRUE, 否则返回FALSE if( S.top = 0 ) return true; else return false; void Push(sqstack *s,elmtype x) if(s-top=MAXSIZE-1) printf(ERROR,Overflow!n); else s-top+; s-stacks-top=x; void Pop(sqstack *s,elmtype *x) if(s-top=0) printf(ERROR,Underflow!n); else *x=s-stacks-top; s-top-; elmtype Gettop(sqstack s) if(s.top=0) printf(ERROR,underflown); return 0; else return s.stacks.top;elmtype f(char c) switch(c) case +: return 0; case -: return 1; case *: return 2; case /: return 3; case (: return 4; case ): return 5; default: return 6; void visitoptr(sqstack c)/对栈进行遍历elmtype s;sqstack m;int i=0;Initstack(&m);if(StackEmpty(c)printf(0);while(!StackEmpty(c) Pop(&c,&s); Push(&m,s);while(!StackEmpty(m)i+;Pop(&m,&s);Push(&c,s); printf(%c,chs); printf(tt);void visitopnd(sqstack c)/对栈进行遍历elmtype s;sqstack m;int i=0;Initstack(&m);if(StackEmpty(c)printf(0);while(!StackEmpty(c) Pop(&c,&s); Push(&m,s);while(!StackEmpty(m)i+;Pop(&m,&s);Push(&c,s); printf(%d ,s); printf(tt);void printstep() n+; printf(%d,n); printf(tt);char Compare(char c1,char c2) int i1=f(c1); int i2=f(c2);/把字符变成数字 if(f1i1f2i2)/通过原来设定找到优先级 return ; else if(f1i1f2i2) return ; else return =;int Operate(elmtype a,elmtype t,elmtype b) int sum; switch(t) case 0: sum=a+b; break; case 1: sum=a-b; break; case 2: sum=a*b; break; default: sum=a/b; return sum;EvaluateExpression() char c; int i=0,sum=0; int k=1,j=1;/设置了开关变量 elmtype x,t,a,b; sqstack OPTR,OPND; Initstack(&OPTR); Push(&OPTR,f(#);/0压入栈 Initstack(&OPND); c=getchar(); printf(*表达式求值演示*n); printf(step); printf(tt); printf(OPTR); printf(tt); printf(OPND); printf(tt); printf(操作n); printstep(); printf(Push(&OPTR,#)n); while(c!=#|chGettop(OPTR)!=#) if(isdigit(c) sum=0; while(isdigit(c) if(!j) sum=sum*10-(c-0);/实现了数字串前面有负号（之前是：sum=-(sum*10)-(c-0)结果是121321） else sum=sum*10+(c-0); c=getchar(); Push(&OPND,sum);/如果还是数字先不压栈，把数字串转化成十进制数字再压栈 j=1; else if(k) switch(Compare(chGettop(OPTR),c) case: Pop(&OPTR,&t); printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Pop(&OPTR,%c)n,cht); Pop(&OPND,&b); printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Pop(OPND,%d)n,b); Pop(&OPND,&a);/注意这里是谁先出栈 printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Pop(&OPND,%d)n,a); Push(&OPND,Operate(a,t,b); printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Push(&OPND,Operate(%d,%c,%d )n,a,cht,b); break; return(Gettop(OPND);main() int result; printf(*欢迎使用表达式求值小程序*n); printf(请输入你的算术表达式(以#号结束)：n); result=EvaluateExpression(); printf(表达式的计算结果是 :%dn,result); printf(*感谢使用表达式求值小程序*n); printf(#班课程设计小组#n); printf(#组员: # # # # # # # # # # # # # #n); printf(# # # # # # # # #n); printf(# # # # # # # # # # #n); printf(# # # #n); printf(#班课程设计小组#n); return 0;/*表达式求值*/六测试分析（运行结果）1. 按照附录中的测试数据，得出如下测试、分析结果：1).3+4*3#请输入你的算术表达式(以#号结束)：3+4*3#*表达式求值演示*step OPTR OPND 操作1 Push(&OPTR,#)2 #+ 3 Push(&OPTR,+)3 #+ 3 getchar()=34 #+* 3 3 Push(&OPTR,*)5 #+* 3 3 getchar()=46 #+ 3 3 4 Pop(&OPTR,*)7 #+ 3 3 Pop(OPND,4)8 #+ 3 Pop(&OPND,3)9 #+ 3 12 Push(&OPND,Operate(3,*,4 )10 # 3 12 Pop(&OPTR,+)11 # 3 Pop(OPND,12)12 # 0 Pop(&OPND,3)13 # 15 Push(&OPND,Operate(3,+,12 )表达式的计算结果是 :152).(9-3)*4+8#请输入你的算术表达式(以#号结束)：(9-3)*4+8#*表达式求值演示*step OPTR OPND 操作1 Push(&OPTR,#)2 #( 0 Push(&OPTR,()3 #( 0 getchar()=94 #(- 9 Push(&OPTR,-)5 #(- 9 getchar()=36 #( 9 3 Pop(&OPTR,-)7 #( 9 Pop(OPND,3)8 #( 0 Pop(&OPND,9)9 #( 6 Push(&OPND,Operate(9,-,3 )10 # 6 Pop(&OPND,4)11 # 6 getchar()=*12 #* 6 Push(&OPTR,*)13 #* 6 getchar()=414 # 6 4 Pop(&OPTR,*)15 # 6 Pop(OPND,4)16 # 0 Pop(&OPND,6)17 # 24 Push(&OPND,Operate(6,*,4 )18 #+ 24 Push(&OPTR,+)19 #+ 24 getchar()=820 # 24 8 Pop(&OPTR,+)21 # 24 Pop(OPND,8)22 # 0 Pop(&OPND,24)23 # 32 Push(&OPND,Operate(24,+,8 )表达式的计算结果是 :323)3*(7-2)#请输入你的算术表达式(以#号结束)：3*(7-2)#*表达式求值演示*step OPTR OPND 操作1 Push(&OPTR,#)2 #* 3 Push(&OPTR,*)3 #* 3 getchar()=(4 #*( 3 Push(&OPTR,()5 #*( 3 getchar()=76 #*(- 3 7 Push(&OPTR,-)7 #*(- 3 7 getchar()=28 #*( 3 7 2 Pop(&OPTR,-)9 #*( 3 7 Pop(OPND,2)10 #*( 3 Pop(&OPND,7)11 #*( 3 5 Push(&OPND,Operate(7,-,2 )12 #* 3 5 Pop(&OPND,4)13 #* 3 5 getchar()=#14 # 3 5 Pop(&OPTR,*)15 # 3 Pop(OPND,5)16 # 0 Pop(&OPND,3)17 # 15 Push(&OPND,Operate(3,*,5 )表达式的计算结果是 :152打印 打印结果正确;3退出能正确退出七总结（收获及体会）数据结构是计算机专业很重要的一门课程，也是必须要熟练掌握的课程，通过这次课程设计对我们的数据结构知识进行了一次全面的综合训练，加深了对数据结构基本概念和基本知识的理解，巩固了课堂上学的知识，掌握了数据结构的一些基本方法，深刻理解了算法，锻炼了自己分析问题解决问题的能力。本次课程设计是完成表达式的求值，表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例子。包含了加，减，乘，除等符号的运算等。数据结构的知识只用到了简单的结构，编写起来比较顺利