数据结构课程设计--表达式求值问题.doc

课程设计(论文)题 目 名 称 表达式求值问题 课 程 名 称 数据结构课程设计 学 生 姓 名 XXX 学 号 xxxxxxxxx 系 、专 业 信息工程系、信息工程类 指 导 教 师 xxxxxx 2010年 1 月 3 日目 录1 问题描述22 需求分析23 概要设计231抽象数据类型定义232模块划分34 详细设计441数据类型的定义442主要模块的算法描述45 测试分析751程序运行结果752程序调试与体会.86 课程设计总结8参考文献8附录（源程序清单）9131 问题描述编写一个表达式求值程序，使输入一个四则运算表达式后，能够返回正确的结果。该表达式由数字09、+、-、*、/、括号组成，且表达式必须正确无误。程序的编写可用到栈或队列的基本算法，求出该表达式的值，并分析算法的时间复杂度和运算的结果。2 需求分析（1）为实现算符优先算法,可以使用两个工作栈。一个称做OPTR，用以寄存运算符;另一个称做OPND;用以寄存操作数或运算结果。算法的基本思想是：首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素; 依次读入表达式中每个字符,若是操作数则OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后做相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为#)。（2）该程序实现表达式的求值问题：从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则混合运算的求值，输出正确的结果。3 概要设计31抽象数据类型定义设定栈抽象数据类型的定义采用两个栈的入栈与出栈的操作来进行“运算符和操作数的配对”。程序中主要用到以下抽象数据类型：1）ADT Stack 数据对象：D ai | ai ElemSet, i=2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： （1）InitStack(&S) 操作结果：构造一个空栈S。 （2）GetTop(S, &e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 （3）Push(&S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 （4）StackEmpty(&s) 初始条件: 栈S已存在。 操作结果:若S为空栈，则返回TRUE, 否则返回FALSE （5）Pop(&S, &e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 ADT Stack32模块划分本程序包括三个模块：（1）主函数模块void main() 输入表达式；根据要求进行转换并求值；输出结果；（2）表达式求值模块-实现具体求值（3）表达式转换模块-实现转换。三模块之间简单调用关系：主函数模块表达式求值模块模块表达式转换图3.2 模块调用图4 详细设计41数据类型的定义（1）栈类型#define MAXSIZE 100typedef int elmtype;struct sqstack elmtype stackMAXSIZE; int top;（2）运算符号类型char ch7=+,-,*,/,(,),#;（3）运算符号优先级类型 int f17=3,3,5,5,1,6,0;/*栈内元素优先级*/int f27=2,2,4,4,6,1,0;/*栈外元素优先级*/42主要模块的算法描述该程序主要由主函数模块、表达式求值模块、表达式转换模块三个个部分组成。（1）主函数及表达式求值模块void main() int result;result=EvaluateExpression(); /*对EvaluateExpression()进行调用*/ （2）表达式求值模块主函数只调用了EvaluateExpression()函数;而其他的函数则由EvaluateExpression()调用了，因此使得主函数十分简洁明了。其中求值函数流程图如下：YYYYNNNNNY定义char cC!=#isdigit(c)SUM=0KERROR!isdigit(c)判断!jsum=sum*10-(c-0)sum=sum*10+(c-0)C=GetChar()Push(&OPND,sum)Return(Gettop(OPND)结 束图4.2 表达式求值模块流程图（3）表达式转换模块void trans(char *exp,char *postexp)在本函数中先初始化一个OP栈，依次读入表达式中的每个字符，若是运算符就进OP栈，若运算符则与OP栈进行比较，直至整个表达式转换完毕。 float compvalue(char *postexp) struct float dataMaxSize; int top; st;5 测试分析51程序运行结果： 52程序调试与体会运用栈的基本操作顺利的解决表达式求值及转换问题，主要利用栈的先进后出结构，执行出栈进栈操作并在出栈时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。系统整体上比较完美，无论是输入、输出，还是整个系统的界面，都非常美观、简洁、大方6 课程设计总结通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及C语言的使用都有了更深的了解。在理论学习和上机实践的各个环节中，通过自主学习和请教陈智、成娅辉老师，我收获了不少。当然也遇到不少问题，也正是因为这些问题引发的思考给我带来了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知从何下手道现在知道如何分析问题，如何用专业知识解决实际问题的转变。我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在实际上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力。所以相信通过此次课程设计实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。在这次短短的课程实践里，我得到了陈智老师的关心和帮助。他给了我们很多的信息，与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到技术上难以解决的问题时，他就会指导我们解决问题，他把自己多年来积累的经验传授给我们，是我们顺利的完成了课程设计的任务。再一次感谢给予我指导及帮助的老师和同学们！ 参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#include #include #include #define MAXSIZE 100typedef int elmtype;typedef struct sqstack 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 sqstackelmtype stackMAXSIZE; int top; void Initstack(sqstack *s) s-top=0;int StackEmpty(sqstack S ) if( S.top=0 ) return 1; else return 0;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; 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;float compvalue(char *postexp) struct float dataMaxSize; int top; st; 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(#); Initstack(&OPND); c=getchar(); while(c!=#|chGettop(OPTR)!=#) if(isdigit(c) sum=0; while(isdigit(c) if(!j) sum=sum*10-(c-0); 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); Pop(&OPND,&b); Pop(&OPND,&a); Push(&OPND,Operate(a,t,b); printf(n); break; return(Gettop(OPND); main() int result; textcolor(GREEN); cprintf(*WELCOME *nr); cprintf(*Input arithmetic expression (end with #)*nr); cprintf(*nr); cprintf(* *nr); result=EvaluateExpression(); textcolor(RED); cprintf(*THE RESULT IS: %d nr,result); textcolor(G