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

井冈山大学电子与信息工程学院数据结构课程设计报告 ( 201 201 年度第一学期)课程名称： 数据结构课程设计 题 目 一： 3.2表达式求值问题 题 目 二： 题 目 三： 院 系： 计算机科学系 班 级： 姓 名： 学 号： 指导教师： 孙凌宇老师 成 绩： 201 年 月 日成 绩 评 定一、 指导教师评语二、 成绩成绩备注 指导教师： 日 期： 年 月 日目 录设计题目： “表达式求值问题”的设计与实现1SLY 数据结构课程设计报告设计题目： “表达式求值问题”的设计与实现1. 设计要求1.1 问题描述任何一个表达式都是由操作数、运算符和界限符组成的。其中，操作数可以是常量，也可以是变量；运算符可以是算术运算符、关系运算符和逻辑运算符；界限符是左右括号和标志表达式结束的结束符。在本课程设计中，仅讨论简单算术表达式的求值问题，约定表达式中只包含加减乘除4种运算，所有的运算对象均为简单变量，表达式的结束符为“#”。要求以字符序列的形式从终端输入语法正确，不含变量的整式表达式。利用已知的运算符优先关系，实现对算术表达式的求值。1.2 需求分析这是一个利用栈结构完成的程序。为了实现算术优先算法，我们使用两个工作栈，一个称为操作符栈（OPTR）,用以寄存运算符；一个称为操作数栈（OPND），用以寄存操作数或运算结果。算法的基本思想是：（1）首先置操作数栈OPND为空栈，表达式结束符“#”为操作符栈OPTR的栈底元素。（2）依次读入表达式中的每个字符，表达式结束符“#”为操作符栈OPTR的栈底元素。栈的栈顶运算符比较优先级后做相应操作，直至整个表达式求值完毕。2. 概要设计2.1主界面设计表达式求值程序界面设计并不复杂，有提示表达式输入及结束符号的信息即可。运行界面如图1所示。图1 表达式求值主菜单 2.2 存储结构设计本系统采用顺序栈结构类型存储表达式计算中的数据。程序中需要建立两个栈，一个栈用来寄存运算符，另一个用来以寄存操作数和运算结果。 2.3 算术优先级设计 对于算术优先级的算法设计，有如下一些关键存储结构和函数。 数组名为ch的数组存放所有运算符，数组名为f1的数组存放栈内运算符的优先级，数组名为f2的数组存放栈外运算符的优先级，通过函数con可将运算符：+，-，*，/，（，），#，转化成数字0，1,2,3，4,5,6，如图2所示。运算符+-*/（）#转化为整形数字0123456栈内操作符的优先级3355160栈外操作符的优先级2244210图2 运算符优先级 当遇到当前运算符c是否入操作符栈（OPNT）时，进行如下操作：（1） 将操作符栈（OPNT）的栈顶运算符和当前运算符c分别通过cton()函数转化成整形数字。假设，用i1表示转化成整形数字的栈顶数字的栈顶运算符，用i2表示转化成整形数字的栈顶数字的当前运算符c。（2） 用Compare()函数比较数组元素f1i1和f2i2的优先级大小。a. 如果f1i1 f2i2,函数返回值为，表示当前运算符的优先级较小，栈顶运算符是目前优先级最大的运算符，因此将进行栈顶运算符出栈并进行相应的运算。具体步骤如下：首先，将操作数栈栈顶元素出栈，并用变量t存放；然后从操作数栈弹出一个栈顶元素并用变量b存放，继续从操作数栈弹出下一个栈顶元素用变量a存放；最后，将a,b两个操作数通过运算符通过运算符t做算术运算，运算结果仍入操作数栈，运算完毕后，继续扫描表达式。b. 如果f1i1f2i2，函数返回值为，表示当前运算符的优先级较大，应继续扫描表达式优先级更大的算出现。此时暂不进行数据运算，只需将当前运算符c入操作符栈。c. 如果f1i1=f2i2，函数返回值为=，表示界限符内的式子已计算完毕，不需要进行数据运算，只需将操作符栈栈顶元素出栈即可。3 模块设计3.1 模块设计 本程序包含3个模块，主程序模块，计算模块和顺序栈操作模块，调用关系如图3所示。主程序模块计算模块顺序栈操作模块图3 模块调用示意图3.2系统子程序及功能设计 本系统共设置10个函数，其中主要包括主函数。各函数及功能说明如下。（1）elemtype cton(char c) /把操作符转换成相应的数字，并返回（2）char Compare(char c1,char c2) /比较原来的设定比较两个字符的优先级（3）int Operate(elemtype a,elemtype t,elemtype b) /进行四则运算，并返回结果（4）int EvaluateExpression()/实现表达式的求值，返回计算结果以下编号（5）（9）是顺序栈的基本操作。（5）elemtype Gettop(sqstack s) /去栈顶元素（6）void Initstack(sqstack *s) /初始化栈（7）void Pop(sqstack *s,elemtype *x) / 出栈（8）void Push(sqstack *s,elemtype x) / 入栈（9）bool StackEmpty(sqstack S ) / 判断栈是否为空（10）void main() /主函数 3.3函数主要调用关系图本系统10个函数之间的主要调用关系如图4所示，图中数字是各函数的编号。10 mian()4 EvaluateExpression()112356789图4 系统函数调用关系图4 详细设计 4.1 数据类型定义（1）顺序栈定义 typedef struct sqstack elemtype stackMAXSIZE; int top;sqstack;（2）全局标量定义 char ch7=+,-,*,/,(,),#;int f17=3,3,5,5,1,6,0;int f27=2,2,4,4,6,1,0;int n=0; 4.2 系统主要子程序详细设计（1）主函数模块设计 主函数。设定用户操作界面的颜色和大小，调用计算模块。main() system(color 1f); /屏幕颜色设定 system(mode con: cols=80 lines=35); char ch;printf(*欢迎使用表达式求值小程序*n);doint result;printf(请输入你的算术表达式(以#号结束)：n);result=EvaluateExpression();printf(表达式的计算结果是 :%dn,result);printf(是否继续(Y|N);doscanf(%s,&ch);if(ch=y|ch=Y)break; else if(ch=n|ch=N)return 0;elseprintf(n输入有误，请重新输入!n);printf(请重新输入:);while(ch!=Y);while(ch!=Y);printf(*感谢使用表达式求值小程序*n); return 0;（2）计算模块设计int EvaluateExpression() char c; int i=0,sum=0; int k=1,j=1;/设置了开关变量 elemtype x,t,a,b; sqstack OPTR,OPND; Initstack(&OPTR); Push(&OPTR,cton(#);/0压入栈 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); break; return(Gettop(OPND);5 测试分析系统运行主界面如图2-1所示。按照提示输入算术表达式，及结束符“#”后进行计算，计算结果如图5-1所示。图5-1 表达式求值结果6 用户手册 （1）本程序执行文件为“表达式求值问题.exe”。（2）所求表达式中只能内包含加减乘除4种运算，所以的运算对象均为简单变量，输入表达式的结束符为“#”。（3）输入表达式时，以“#”结束，然后输入回车键即可得到结果。7调试报告 （1）可以把两个或者多个无关的数据用数组练习起来，用它的下标就可以完成。数字与字符的转换，可以表示成字符，但实际运用时用其实际含义。（2）理解实验原理，理解加减乘除在栈内外的大小顺序，然后构造数组。（3）栈的重要性，基础知识的重要性，只有在基础知识上才能有些实现更复杂的操作。 8 程序清单#include #include #include /判断是否为字符的函数的头文件#include#define MAXSIZE 100typedef int elemtype;char ch7=+,-,*,/,(,),#;/把符号转换成一个字符数组int f17=3,3,5,5,1,6,0;/栈内元素优先级int f27=2,2,4,4,6,1,0;/栈外的元素优先级int n=0;typedef struct sqstack elemtype stackMAXSIZE; int top;sqstack;void Initstack(sqstack *s) s-top=0;bool StackEmpty(sqstack S ) /若S为空栈，则返回TRUE, 否则返回FALSEif( S.top = 0 )return true;elsereturn false;void Push(sqstack *s,elemtype x) if(s-top=MAXSIZE-1) printf(ERROR,Overflow!n); else s-top+; s-stacks-top=x; void Pop(sqstack *s,elemtype *x) if(s-top=0) printf(ERROR,Underflow!n); else *x=s-stacks-top; s-top-; elemtype Gettop(sqstack s) if(s.top=0) printf(ERROR,underflown); return 0; else return s.stacks.top;elemtype cton(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=cton(c1); int i2=cton(c2);/把字符变成数字 if(f1i1f2i2)/通过原来设定找到优先级 return ; else if(f1i1f2i2) return