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

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

《数据结构课程设计报告表达式求值问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告表达式求值问题.docx（7页珍藏版）》请在冰点文库上搜索。

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

《数据结构》

课程设计报告

题目：

表达式求值问题

学院（系）：

数学与计算科学学院

班级：

11级信息与计算科学4班

学生学号：

1107020432

姓名：

杨宇红

指导教师：

彭叶辉

2013年6月28日

摘要………………………………………………………………………2

一、需求分析……………………………………………………………2

二、概要设计……………………………………………………………2

三、详细设计……………………………………………………………5

1、预定义和定义结构体 ……………………………………………………5

2、基本操作的算法描述 ……………………………………………………5

3、判断输入的运算符是否在运算符允许范围内…………………………………6

4、比较运算符间的优先关系…………………………………………………7

5、确定两运算数之间的运算符后进行运算，并返回两操作数运算后的结果  ………7

6、提示用户按照要求输入正确的表达式 ………………………………………8

7、遵循算术运算规则求解表达式 ……………………………………………9

8、输出运算结果 …………………………………………………………9

四、设计和调试分析……………………………………………………9

五、用户手册……………………………………………………………10

六、测试结果……………………………………………………………10

七、设计心得……………………………………………………………12八、参考文献……………………………………………………………12九、附录…………………………………………………………………12

摘 要

通过数据结构这门课程，我们较深入的了解到了栈，栈是一种重要的线性结构，它广泛应用于各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。

栈是限定仅在表尾进行插入或删除操作的线性表。

因此，栈又称为后进先出的线性表。

它的这个特点可以应用于多种实际问题，比如数制转换、括号匹配的检验、行编辑程序、迷宫求解以及表达式求值等问题。

本次试验我们将探索表达式求值问题，表达式求值是程序设计语言编译中的一个最基本的问题，它的实现是栈应用的又一个典型的例子。

通过实验我们能用程序计算带括号的表达式，在过程中更深入的了解到栈的基本操作。

关键词：

栈、先进后出、带括号的表达式、表达式求值、

一、需求分析 

本程序用于解决一个可以带括号的表达式求值的问题，要运用到栈，而且会用到一种简单直观，广为使用的算法，通常称为“算符优先法”。

进行表达式求值首先要了解算术四则运算的规则。

即：

（1）先乘除，后加减；

（2）从左算到右；（3）先括号内后括号外；算符优先法根据这个算符优先关系的规定来实现对表达式的编译或解释执行的。

任何一个表达式都是由操作数、运算符和界限符组成。

为实现算符优先算法，可以使用两个工作栈。

一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。

算法的基本思想是：

（1）首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；

（2）一次读入表达式中每个字符，若是操作数则进OPND栈若是运算符则和OPTR栈的栈顶元素比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。

界面要求使用VC++6.0的运行环境。

二、概要设计

1、栈抽象数据类型的定义如下：

ADTStack{

数据对象：

D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系：

R1={|ai-1,ai∈D,i=1,2,…,n}

约定an端为栈顶，a1端为栈底。

基本操作：

InitStack（&S）

操作结果：

构造一个空栈S。

DestroyStack（&S）

初始条件：

栈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返回其值。

StackTraverse（S,visit（））

初始条件：

栈S已存在且非空。

操作结果：

从栈底到栈顶依次对S的每个数据元素调用函数visit（）。

一旦visit（）失败，   则操作失败。

}ADTStack

2、本程序调用的函数如下：

charPrecede（chara,charb）；//用于比较运算符间优先关系

floatyunsuan（floata,charzhi,floatb）；确定a、b间的运算数符运算a、b两个运算数并将结果赋给zhi

floatEvalueateExpression（sqstackOPND,SqstackOPTR）；

//算术表达式求值的算符优先算法。

设OPTR和OPND分别为运算栈符和运算数符

printf（"请输入表达式并以#结束,其中数字在1-9中选择\n"）;//打印出界面提示

printf（"结果是:

%.2f\n",m）;//打印出结果

intIn（charc）；//判断运算符的是否符合条件

3、栈基本操作的函数调用

intInitstack1（Sqstack&OPTR）；//构造一个空栈OPTR

intPush（Sqstack&OPTR,chare）；//插入元素e为新的栈顶元素

intPop（Sqstack&OPTR,char&e）；//若栈不空，则删除OPTR的栈顶元素，用e返回其值，并返回OK；否则返回ERROR

charGetTop1（Sqstack&OPTR）；//若栈不空，则返回s的栈顶元素，并返回OK；否则返回ERROR

4、主函数

intmain（）

{

floatm;

SqstackOPTR;

sqstackOPND;

Initstack（OPND）;

Initstack1（OPTR）;

printf（"请输入表达式并以#结束,其中数字在1-9中选择\n"）;

m=EvalueateExpression（OPND,OPTR）;

printf（"结果是:

%.2f\n",m）;

return0;

}

三、详细设计

1、预定义和定义结构体

#defineSTACK_INIT_SIZE100 

#defineSTACKINCREMENT10  

#defineOVERFLOW -2

#define OK  1

#define ERROR 0

#define TRUE  1

#define   FALSE  0

typedefstruct

{

float*base;

float*top;

intstacksize;

}sqstack;

typedefstruct

{

char*base;

char*top;

intstacksize;

}Sqstack;

2、基本操作的算法描述

intInitstack（sqstack&S）

{//构造一个空栈s

S.base=（float*）malloc（STACK_INIT_SIZE*sizeof（float））;

if（!

S.base）

exit（OVERFLOW）;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}

intPush（sqstack&S,floate）

{//插入元素为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.top++=e;

returnOK;

}

intPop（sqstack&S,float&e）

{//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR

if（S.top==S.base）

returnERROR;

e=*--S.top;

returnOK;

}

floatGetTop（sqstack&S, float&e）

{//若栈不空，则用e返回s的栈顶元素，并返回OK；否则返回ERROR

if（S.top==S.base）

returnERROR;

e=*（S.top-1）;

returnOK;

}

3、判断输入的运算符是否在运算符允许范围内

intIn（charc）

{

if（c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='（'||c=='）'）//表达式中可以出现的运算符

returnTRUE;

else

returnFALSE;

}

4、比较运算符间的优先关系

charPrecede（chara,charb）

{

inti,j;

charop[8][8]={{'','+','-','*','/','（','）','#'},

{'+','>','>','<','<','<','>','>'},

{'-','>','>','<','<','<','>','>'},

{'*','>','>','>','>','<','>','>'},

{'/','>','>','>','>','<','>','>'},

{'（','<','<','<','<','<','=',''},

{'）','>','>','>','>','','>','>'},

{'#','<','<','<','<','<','','='}};//OP为运算符集合 运算符间的优先关系