2022/4/25 20:18:00
软 件 学 院
课程名称设计题目专业班级学 号姓 名指导教师
课程设计报告书
数据结构 算术表达式求值演示程序
2010年 12月
目录
1.设计时间 2 2.设计目的 2 3.设计任务 2 4.设计内容 2
4.1需求分析 2 4.2总体设计 2
4.2.1抽象数据类型定义 2 4.2.2函数模块说明 3 4.2.3主函数流程图 4
4.2.4函数模块调用关系 5 4.2.5运算符间的优先关系 5
4.3详细设计 6
4.3.1数据类型的定义 6 4.3.2函数调用关系 8
4.3.3主要模块的算法描述 8
4.4测试与分析 10
4.4.1测试 10 4.4.2分析 11
4.5附录
11
5.总结与展望 16
参考文献 17 成绩评定 17
1
1 设计时间 2010.12.27-2011.1.3 2 设计目的 掌握栈的使用和把一个表达式翻译成能够正确求值的一个机器指令序列的原理。 3设计任务 设计一个程序，演示用算符优先法对算术表达式求值的过程。 4 设计内容 4.1需求分析 1、程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是还语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。 2、输入的形式和输入值的范围：以字符串的形式输入表达式，以“#”结束。 3、输出的形式：在计算过程中遇到的问题或最终的答案将显示在屏幕上，同时所计算的表达式的最终的结果也将保存在文件中。 4、测试数据：输入“3*(7-2)#”时，输出“15.000000”，测试正确；输入“!(9-2)#”时，输出“输入错误！”，测试正确。 4.2总体设计 4.2.1抽象数据类型定义 ADT Stack{ 数据对象：D={ai |ai∈ElemSet,i=1,2,…，n, n≧0} 数据对象：R1={ 2 操作结果：用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 4.2.2函数模块说明 为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是： (1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素 (2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。 算法中还调用了两个函数。其中Precede是判定运算符栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；Operateo为进行二元运算aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。 4.2.3主函数流程图 3 开始 Char c; SqStack OPTR,OPND;c=getchar() 结束 Return GetTop(OPND) Push(OPTR,c) C=getchar() C!=’#’||GetTop(OPTR)!=’#’ c>=’0’&&c<=’9’ Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,tehta,b)); Precede(GetTop(OPTR),c) Pop(OPTR,c) 4.2.4函数模块调用关系 4 主程序模块 栈的建立及初始化模块 判断输入是否结束模块 判断字符类型模块 运算数进栈模块 运算符优先级比较模块 运算符进栈模块 运算符运算数出栈模块 运算模块 输入结束 输出结果 4.2.5运算符间的优先关系 θ1 θ2 + - * / ( ) # + > > > > < > < - > > > > < > < * > > > > < > < / < < > > < > < ( < < < < < < ) > > > > = > # > > > > > = 4.3详细设计 4.3.1数据类型的定义及基本操作 5 //===== ADT Stack的表示与实现 ===== //----- 栈的顺序存储表示 ----- #define STACK_INIT_SIZT 100; #define STACKINCREMENT 10 typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; //----- 基本操作的算法描述 ----- Status InitStack(SqStack &S){ S.base = (SElemType * )malloc(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.top-1); return OK; } Status Push(SqStack &S,SElemType e){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc(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; } 6 OperandType EvaluateExpession(){ InitStack(OPTR); Push(OPTR,’#’); InitStack(OPND); c = getchar(); while(c!’#’||GetTop(OPTR)!=’#’){ if(!In(c,OP)){Push((OPND,c); c = getchar();) else switch(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,Operate(a,theta,b)); break; } } } 4.3.2函数调用关系 7 main() SqStack C=getchar() InitStack c Push_N(&OPND,i) switch(Predece(GetTop_T(&OPTR),c)) theta=Pop_T(&OPTR); b=Pop_N(&OPND);a=Pop_N(&OPND); Push_N(&OPND,Operate(a,theta,b)) Push_T(&OPTR,c) GetTop_N(&OPND) 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>=47&&c<=57)) { while(c!=’#’||GetTop_T(&OPTR)!=’#’) { if(c>=48&&c<=57) { i=(float)c-48; 8 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(“结果是%f\\n”,GetTop_N(&OPND)); } else printf(“输入错误！\\n”); } 4.4测试与分析 4.4.1测试 加法测试，输入正确，输出正确，测试正确： 减法测试，输入正确，输出正确，测试正确： 9 乘法测试，输入正确，输出正确，测试正确： 除法测试，输入正确，输出正确，测试正确： 输入表达式正确，输出正确，测试正确： 输入表达式错误，能正确判断，测试正确： 4.4.2分析 内容包括： 1、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析: 遇到的问题：调试过程中遇到了输入非法字符不输出“错误！”的情况。 解决的办法：查ASCII码表得知运算符’+’,’-‘,’*’,’/’,’(‘,’)’,’#’和运算数’0’,’1’,’2’,’3’,’4’,’5’,’6’,’7’,’8’,’9’相应的ASCII值。在主程序中加入了判断语句，判断输入的是否为运算符或运算数。如果是，则进行正常运算；如果不是，则返回错误。 2、算法的时间复杂度和空间复杂度的分析： 中缀表达式运算时间主要用在字符串扫描和算符优先权的比较上。把#看作运算符，操作数与运算符个数相同，最坏情况下优先级比较是n/2次，即运算顺序完全是逆序的，每个字符扫描一遍是O(n)的，所以整个算法复杂度是O(n2)的。算法中用到两个栈，分别为O(n/2)， 10 其算法空间复杂度是O(n)。 4.5附录 #include \"stdio.h\" #include \"stdlib.h\" #define OK 1 #define ERROR 0 #define OVERFLOW 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base; char *top; int stacksize; }SqStack_T; typedef struct{ float *base; float *top; int stacksize; }SqStack_N; void InitStack_T(SqStack_T *S){ (*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(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_SIZE*sizeof(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).base) return ERROR; e=*((*S).top-1); return e; } 11 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(OVERFLOW); (*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).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); 12 return e; } char m[7]=\"+-*/()#\"; char n[7][7]={\">><<<>>\",\">><<<>>\",\">>>><>>\",\">>>><>>\",\"<<<<<= \" ,\">>>> >>\",\"<<<<< =\"}; char Precede(char a,char b){ int i=0,j=0; while(m[i]!=a) i++; while(m[j]!=b) j++; return(n[i][j]); } float Operate(float a,char theta,float b){ float r; switch(theta){ case'+':r=a+b;break; case'-':r=a-b;break; case'*':r=a*b;break; case'/':if(b!=0)r=a/b; } return r; } void main(){ SqStack_T OPTR; SqStack_N OPND; float a,b,i; char theta,c,x; else printf(\"输入错误!\"); break; InitStack_T(&OPTR);Push_T(&OPTR,'#'); InitStack_N(&OPND); printf(\"请输入表达式并以'#'结尾:\\n\"); c=getchar(); if(c==35||(c>=40&&c<=43)||c==45||(c>=47&&c<=57)) { while(c!='#'||GetTop_T(&OPTR)!='#') { 13 if(c>=48&&c<=57) { } else { i=(float)c-48; Push_N(&OPND,i); c=getchar(); switch(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(&OPTR);b=Pop_N(&OPND); a=Pop_N(&OPND); Push_N(&OPND,Operate(a,theta,b));break; } } }printf(\"结果是%f\\n\",GetTop_N(&OPND)); } else printf(\"输入错误!\\n\"); } } 5 总结与展望 通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及C语言的使用都有了更深的了解。当然也遇到不少问题，也正是国为这些问题引发的思考给我带来了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知从何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变。我发现无论是专业知识还是动手能力，自己都有很大程度的提高。 在实际上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，为后续课程的学习及实践打下良好的基础。 这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构的紧密联系。设计题目不仅要求设计者对课本知识有较深刻的了解，同时要有较强的思维动手能力。 这次的课程设计让我有一个深刻的体会：严谨！编程最需要的就是严谨，往往检查到的错误是在某个括号、分号、引号等不应该犯错的地方上。 程序设计时难免遇到错误，但这不是坏事情，它可以让我发现自己的薄弱环节，在具体操作中还可以巩固所学的C及数据结构。更加体会到了C的语句简洁、使用灵活、执行效率高等特点。 14 参考文献 [1] 严蔚敏.吴伟民.数据结构(C语言版).北京:清华大学出版社,2007 [2] 谭浩强著.C程序设计(第二版).北京:清华大学出版社,2005 成绩评定 成绩 教师签字 15 因篇幅问题不能全部显示，请点此查看更多更全内容