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

1、数据结构课程设计报告表达式求值问题数据结构课 程 设 计 报 告题 目： 表达式求值问题 学院（系）： 数学与计算科学学院班 级： 11级信息与计算科学4班 学生学号： 1107020432 姓 名： 杨宇红 指导教师： 彭叶辉 2013年 6月28 日摘要2一、需求分析2二、概要设计2三、详细设计51、预定义和定义结构体 52、基本操作的算法描述 53、判断输入的运算符是否在运算符允许范围内 64、比较运算符间的优先关系 75、确定两运算数之间的运算符后进行运算，并返回两操作数运算后的结果 76、提示用户按照要求输入正确的表达式 87、遵循算术运算规则求解表达式 98、输出运算结果 9四、设

2、计和调试分析9五、用户手册10六、测试结果10七、设计心得12八、参考文献12九、附录12摘 要通过数据结构这门课程，我们较深入的了解到了栈，栈是一种重要的线性结构，它广泛应用于各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。栈是限定仅在表尾进行插入或删除操作的线性表。因此，栈又称为后进先出的线性表。它的这个特点可以应用于多种实际问题，比如数制转换、括号匹配的检验、行编辑程序、迷宫求解以及表达式求值等问题。本次试验我们将探索表达式求值问题，表达式求值是程序设计语言编译中的一个最基本的问题，它的实现是栈应用的又一个典型的例子。通过实验我们能用程序计算带括号的表达式，在过程中更深入

3、的了解到栈的基本操作。关键词：栈、先进后出、带括号的表达式、表达式求值、一、需求分析 本程序用于解决一个可以带括号的表达式求值的问题，要运用到栈，而且会用到一种简单直观，广为使用的算法，通常称为“算符优先法”。进行表达式求值首先要了解算术四则运算的规则。即：(1）先乘除，后加减；（2）从左算到右；（3）先括号内后括号外；算符优先法根据这个算符优先关系的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由操作数、运算符和界限符组成。为实现算符优先算法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：（1）首先置操作数栈为

4、空栈，表达式起始符“#”为运算符的栈底元素；（2）一次读入表达式中每个字符，若是操作数则进OPND栈若是运算符则和OPTR栈的栈顶元素比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。界面要求使用VC+6.0的运行环境。二、概要设计1、栈抽象数据类型的定义如下：ADT Stack数据对象：D=ai|aiElemSet, i=1,2, ,n, n0数据关系：R1=|ai-1,aiD, i=1,2, ,n 约定an端为栈顶，a1端为栈底。基本操作：InitStack( &S )操作结果：构造一个空栈S。DestroyStack ( &S )初始条件

5、：栈S已存在。操作结果：销毁栈S。ClearStack( &S )初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty( S )初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。StackLength( S )初始条件：栈S已存在。操作结果：返回S的数据元素个数，即栈的长度。GetTop( S, &e )初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push( &S, e )初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop( &S, &e )初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。Stac

6、kTraverse( S, visit() )初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败， 则操作失败。ADT Stack2、本程序调用的函数如下：char Precede(char a,char b)；/用于比较运算符间优先关系float yunsuan(float a,char zhi , float b)；确定a、b间的运算数符运算a、b两个运算数并将结果赋给zhi float EvalueateExpression(sqstack OPND,Sqstack OPTR)；/算术表达式求值的算符优先算法。设OPTR

7、和OPND分别为运算栈符和运算数符printf(请输入表达式并以#结束,其中数字在1-9中选择n);/打印出界面提示printf(结果是:%.2fn,m);/打印出结果int In(char c)；/判断运算符的是否符合条件3、栈基本操作的函数调用int Initstack1(Sqstack &OPTR)；/构造一个空栈OPTRint Push(Sqstack &OPTR,char e)；/插入元素e为新的栈顶元素int Pop(Sqstack &OPTR,char &e)；/若栈不空，则删除OPTR的栈顶元素，用e返回其值，并返回OK；否则返回ERRORchar GetTop1(Sqstac

8、k &OPTR)；/若栈不空，则返回s的栈顶元素，并返回OK；否则返回ERROR4、主函数int main()float m;Sqstack OPTR;sqstack OPND;Initstack(OPND);Initstack1(OPTR);printf(请输入表达式并以#结束,其中数字在1-9中选择n);m=EvalueateExpression(OPND,OPTR);printf(结果是:%.2fn,m);return 0;三、详细设计1、预定义和定义结构体#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVER

9、FLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef structfloat *base;float *top;int stacksize;sqstack;typedef structchar *base;char *top;int stacksize;Sqstack;2、基本操作的算法描述int Initstack(sqstack &S)/构造一个空栈sS.base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!S.base)exit(OVERFLOW

10、);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int Push(sqstack &S,float e)/插入元素为e的栈顶元素if(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(float *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(float);if(!S.base)exit (OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.t

11、op+=e;return OK;int Pop(sqstack &S,float &e)/若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base)return ERROR;e=*-S.top;return OK;float GetTop(sqstack &S, float &e)/若栈不空，则用e返回s的栈顶元素，并返回OK；否则返回ERRORif(S.top=S.base)return ERROR;e= *(S.top-1);return OK;3、判断输入的运算符是否在运算符允许范围内int In(char c)if(c=+|c=-|c=*|c=/|c=#|c=(|c=)/表达式中可以出现的运算符return TRUE;elsereturn FALSE;4、比较运算符间的优先关系char Precede(char a,char b)int i,j;char op88= ,+,-,*,/,(,),#,+, -,*,/,(, ,#, ,=;/OP为运算符集合 运算符间的优先关系