数据结构课程设计报告-算术表达式求值演示程序

1、软件学院课程设计报告书课程名称 数据结构 设计题目 算术表达式求值演示程序专业班级 学 号 姓 名 指导教师 2010年12月目录1。设计时间22。设计目的23。设计任务24。设计内容24.1需求分析24.2总体设计24。2。1抽象数据类型定义24。2.2函数模块说明34。2。3主函数流程图44。2。4函数模块调用关系54。2。5运算符间的优先关系54。3详细设计64。3。1数据类型的定义64.3.2函数调用关系84。3.3主要模块的算法描述84。4测试与分析104。4.1测试104。4.2分析114。5附录115.总结与展望16参考文献17成绩评定171 设计时间2010.12.272011

2、。1.32 设计目的掌握栈的使用和把一个表达式翻译成能够正确求值的一个机器指令序列的原理。3设计任务设计一个程序，演示用算符优先法对算术表达式求值的过程。4 设计内容4。1需求分析1、程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数,判断表达式是还语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储.2、输入的形式和输入值的范围：以字符串的形式输入表达式,以“"结束。3、输出的形式:在计算过程中遇到的问题或最终的答案将显示在屏幕上，同时所计算的表达式的最终的结果也将保存在

3、文件中.4、测试数据:输入“3*(7-2)#”时，输出“15.000000”，测试正确；输入“！（9-2）”时，输出“输入错误！”，测试正确。4。2总体设计4。2。1抽象数据类型定义ADT Stack数据对象：D= |ElemSet，i=1，2，,n， n0数据对象：R1=>，,i=2,，n约定端为栈顶，端为栈底。基本操作：InitStack（&S)操作结果：构造一个空栈S。GetTop（S）初始条件：栈S已存在。操作结果：用P返回S的栈顶元素。Push（S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop（S)初始条件：栈S已存在.操作结果：删除S的栈顶

4、元素.In（ch)操作结果:判断字符是否是运算符，运算符即返回1。Precede(c1， c2）初始条件:c1，c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate（a，op，b）初始条件：a，b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n）操作结果:返回操作数的长度。EvalExpr（）初始条件：输入表达式合法.操作结果:返回表达式的最终结果。ADT Stack4。2。2函数模块说明为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果.算法的基本思想是：（1)首先置操作

5、数栈为空栈，表达式起始符“"为运算符栈底元素（2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#”).算法中还调用了两个函数。其中Precede是判定运算符栈顶运算符1与读入的运算符2之间优先关系的函数;Operateo为进行二元运算ab的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名;如果是解释执行表达式，则直接进行该运算，并返回运算结果.4.2。3主函数流程图4.2.4函数模块调用关系4。2。5运算符间的优先关系1

6、 2+-/（)+><>->/><（<<=）><<=4。3详细设计4。3。1数据类型的定义及基本操作/= ADT Stack的表示与实现 = /- 栈的顺序存储表示 -define STACK_INIT_SIZT 100;define STACKINCREMENT 10typedef structSElemType base；SElemType *top；int stacksize；SqStack;/- 基本操作的算法描述 -Status InitStack（SqStack &S）S。base=(SElemType )ma

7、lloc（STACK_INIT_SIZE * sizeof（SElemType）)；if(!S。base） exit (OVERFLOW)；S。top=S。base;S。stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack S,SElemType e)if（S。top=S。base） return ERROR;e=（S。top1）;return OK;Status Push(SqStack &S，SElemType e)if（S。topS.base=S。stacksize) S。base=（SElemType)realloc

8、（S。base，(S。StackSize+STACKINCREMENT）sizeof （SElemType）；if(！S。base） exit(OVERFLOW）; S。top=S。base+S。stacksize； S。stacksize += STACKINCREMENT；S.top+ =e;return OK；Status Pop（SqStack &S,SElemType e）if(S。top = S。base) return ERROR；e = * -S。top;return OK；OperandType EvaluateExpession（）InitStack(OPTR）；

9、Push(OPTR，#);InitStack（OPND）； c = getchar（）；while（c！|GetTop（OPTR）！='#）if(!In(c,OP）)Push(（OPND，c）; c = getchar();）elseswitch（Precede(GetTop(OPTR），c）)case：Push（OPTR,c）； c = getchar(）； break；case=：Pop（OPTR,x）； c = getchar（）； break;case'：Pop（OPTR，theta）； Pop（OPND,b）; Pop(OPND，a）； Push（OPND，Opera

10、te(a，theta，b）; break; 4。3。2函数调用关系4。3.3主要模块的算法描述void main（)SqStack_T OPTR；SqStack_N OPND;float a,b，i；char theta,c,x；InitStack_T(&OPTR）；Push_T（OPTR，')；InitStack_N（OPND)；printf（“请输入表达式关以'#结尾：n”)；c=getchar（）；if（c=35（c=40&&c=43)c=45|(c=47c=57)）while(c！='|GetTop_T(OPTR）!=)if(c=48&a

11、mp;c<=57) i=（float)c48； Push_N（OPND，i)； c=getchar（）; else switch（Precede（GetTop_T（OPND），c） case'：Push_T(OPTR,c）;c=getchar（)；break；case'=:x=Pop_T（&OPTR）;c=getchar(）;break;case''：theat=Pop_T（OPTR）；b=Pop_N（OPND）；a=Pop_N（OPND）；Push_N(OPND，Operate（a，theta，b）；break； printf（“结果是%fn”，

12、GetTop_N（&OPND);else printf(“输入错误！n”）；4。4测试与分析4.4.1测试加法测试,输入正确，输出正确,测试正确：减法测试，输入正确，输出正确，测试正确：乘法测试，输入正确，输出正确，测试正确：除法测试，输入正确，输出正确，测试正确:输入表达式正确，输出正确，测试正确:输入表达式错误,能正确判断,测试正确:4。4。2分析内容包括：1、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:遇到的问题：调试过程中遇到了输入非法字符不输出“错误!”的情况。解决的办法：查ASCII码表得知运算符'+'，'/，'(,&#

13、39;）,'和运算数'0，1',2，3，'4，5，6'，7',8'，9相应的ASCII值。在主程序中加入了判断语句,判断输入的是否为运算符或运算数。如果是，则进行正常运算;如果不是，则返回错误。2、算法的时间复杂度和空间复杂度的分析：中缀表达式运算时间主要用在字符串扫描和算符优先权的比较上.把#看作运算符，操作数与运算符个数相同，最坏情况下优先级比较是n/2次,即运算顺序完全是逆序的，每个字符扫描一遍是O(n）的,所以整个算法复杂度是O（n2）的。算法中用到两个栈，分别为O（n/2),其算法空间复杂度是O（n）。4.5附录include”

14、stdio。h”include”stdlib。h”define OK 1define ERROR 0define OVERFLOW 0define STACK_INIT_SIZE 100define STACKINCREMENT 10typedefstructchar*base；char*top；int stacksize；SqStack_T;typedefstructfloat*base；floattop;int stacksize；SqStack_N；void InitStack_T（SqStack_T S）（S）。base=（char*)malloc（STACK_INIT_SIZE*si

15、zeof(char）；if（!(*S）。base） exit（OVERFLOW)；(*S）。top=（S）.base;（S）。stacksize=STACK_INIT_SIZE；void InitStack_N（SqStack_N *S)（*S)。base=（float）malloc（STACK_INIT_SIZEsizeof(float)）;if(！（S).base) exit（OVERFLOW）;（S）。top=(S）。base;（S).stacksize=STACK_INIT_SIZE；char GetTop_T(SqStack_T S）char e；if（(S）。top=（S）.bas

16、e) return ERROR；e=（S）。top-1）；return e；float GetTop_N(SqStack_N S）float e；if（*S）。top=（S)。base) return ERROR;e=*(*S）。top-1)；return e；char Push_T（SqStack_T S，char e)if（S)。top(S）。base>=（S）。stacksize）(S).base=(char*）realloc（(S)。base，（*S).stacksize+STACKINCREMENT)sizeof(char)）;if（！（*S）.base） exit（OVERF

17、LOW)；（*S)。top=（*S）。base+（S）。stacksize；（S).stacksize+=STACKINCREMENT；(*S）.top）+=e；return OK;float Push_N（SqStack_N S,float e）if（S）。top(S）.base>=（*S)。stacksize）（S).base=（float）realloc（S）。base，（S）。stacksize+STACKINCREMENT）sizeof（float）；if(！（S).base） exit（OVERFLOW）;（S)。top=（S）。base+（*S)。stacksize；(*S

18、)。stacksize+=STACKINCREMENT;（(*S)。top）+=e;return OK;char Pop_T（SqStack_T *S)char e；if(（S）。top=（*S）.base） return ERROR；e=（-（S)。top）;return e;float Pop_N（SqStack_N S）float e；if（S).top=（*S）。base） return ERROR；e=(-（S)。top）；return e；char m7=”+/（）”；char n77=”><>”，”<<<>”，”，”>><

19、;>>”，”= ",">>>> >>”,"<< =”；char Precede(char a,char b）int i=0，j=0;while（mi！=a)i+；while(mj!=b)j+;return(nij）；float Operate（float a,char theta,float b)float r;switch(theta）case+：r=a+b;break;case'：r=ab;break；case*：r=ab；break;case/：if（b！=0）r=a/b；else prin

20、tf（”输入错误!");break；return r;void main(）SqStack_T OPTR；SqStack_N OPND;float a,b，i；char theta，c，x;InitStack_T（OPTR）；Push_T（OPTR，')；InitStack_N（OPND）；printf(”请输入表达式并以''结尾：n”)；c=getchar（）;if（c=35（c=40c=43）c=45|（c=47&c<=57）while（c!=GetTop_T（OPTR）!='#）if（c=48&c=57）i=（float）c48;Push_N（&OPND,i）;c=getchar(）;elseswitch（Precede(GetTop_T(&OPTR),c）)case：Push_T(&OPTR，c）；c=getchar（）；break;case'='：x=Pop_T（OPTR）；c=getchar()；break；case>：theta=Pop_T