数据结构实验.docx
《数据结构实验.docx》由会员分享，可在线阅读，更多相关《数据结构实验.docx（12页珍藏版）》请在冰点文库上搜索。
数据结构实验
数据结构实验报告
班级：
igot7
姓名：
鸟宝宝
实验目的：
熟练掌握栈的基本操作，进一步理解栈的应用。
实验内容：
设计一个程序，用算符优先算法对算术表达式求值。
基本要求：
以字符序列的形式从终端输入语法正确的、不含变量的算术表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。
实现提示：
1．利用栈辅助分析算符优先关系；
2．在读入表达式字符序列的同时，完成运算符和操作数的识别处理，以及相应的运算；
3．在识别出操作数的同时，要将其字符序列形式转换成相应的浮点数形式（该条件可放宽为只处理“0”到“9”共10个整数）。
测试数据：
8.25;
1+2.5+3＋4;
8.7-1*5.2;
1024/4*8;
1024/（4*8）;
（17.7+2.3）*（6/2）;
3-3-3;
8/（9-9）;
设计过程
要想实现算符优先算法，使用两个栈，一个是OPND，用来存放操作数或者计算的结果，一个是OPTR，用来存放运算符。
首先先建立两个空栈，将“#”作为OPTR的栈底元素。
然后依次读入表达式的每个字符，如果是操作数就直接读入OPND栈，如果是运算符就进行优先级比较，若比OPTR的栈顶元素优先级大，则该运算符进栈；反之，OPTR栈顶运算符出栈，同时OPND栈顶上的两个元素也出栈，调用函数进行运算，并且每次运算结果进OPND栈。
直到OPTR栈的栈顶运算符号与当前读入的运算符号都是"#"，表达式计算完毕，程序结束。
ADTStack{
数据对象：
D={ai|ai∈ELemSet,i=1,2,…,n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=2,…,n}
约定an端为栈顶，ai端为栈底。
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefstruct
{
SElemType*top;
SElemType*base;
intstacksize;
}SqStack;
StatusInitStack（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;
returnOK;
}//INitstack
SElemTypeGetTop（SqStackS）
{//若栈不空,用e返回栈顶元素,并且返回OK,否则返回ERROR
SElemTypee;
if（S.top==S.base）returnERROR;
e=*（S.top-1）;
returne;
}//GetTop
StatusStackEmpty（SqStackS）
{
if（S.top==S.base）returnOK;
elsereturnERROR;
}
StatusPush（SqStack&S,SElemTypee）
//插入为新的栈顶元素
{
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;
returnOK;
}//Push
StatusPop（SqStack&S,SElemType&e）
{//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if（S.top==S.base）returnERROR;
e=*--S.top;
returnOK;
}//Pop
charEvaluateExpression（）
{//算术表达是求值的算符优先算法。
OPTR和OPND分别为运算符栈和运算数栈
//OP为运算符集合
SqStackOPTR,OPND;
InitStack（&OPTR）;Push（&OPTR,'#'）;
InitStack（&OPND）;
printf（"请输入算术表达式：
以#结束。
\n"）;
c=getchar（）;
while（c!
='#'||GetTop（OPTR）!
='#'）
{
if（!
In（c））
{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;
}//switch
}//while
returnGetTop（OPND）;
}//EvaluateExpression
两个函数：
Operate为进行二元运算a○b的函数
charOperate（chara,SElemTypetheta,charb）
{//数值计算
intz;
switch（theta）
{case'+':
z=a+b;break;
case'-':
z=b-a;break;
case'*':
z=a*b;break;
case'/':
z=b/a;break;
}
returnz;
}
Precede是判定运算符栈的栈顶运算符与读入的运算符之间优先关系的函数
charPrecede（charc1,charc2）
{//c1的优先权与c2优先权的判断
inti,j;
chara[7][7]={
//运算符的优先关系表格
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='}};
i=Transfor（c1）;
j=Transfor（c2）;
return（a[i][j]）;
}
调试过程
在调试过程中，对于大部分数据运算结果是可信的，但在测试的途中发现很多异常。
例如输入的算数表达式仅仅只含有单个操作数时，并不能得到正确的答案。
在对表达式求值过程中产生了没有意义或者超出范围的数缺乏异常处理，从而导致程序运行不稳定。
在设计GetTopde函数时，发现如果用e返回栈顶元素反而使得问题变得复杂。
于是舍弃了参数e，在函数体中定义了e,并将其值作为返回值。
源代码及清单
#include
#include
#defineOVERFLOW-1
#defineOK1
#defineTRUE1
#defineFALSE0
#defineERROR0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineNULL0
typedefcharSElemType;
typedefintStatus;
typedefstruct
{
SElemType*top;
SElemType*base;
intstacksize;
}SqStack;
StatusInitStack（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;
returnOK;
}
StatusDestroyStack（SqStack*S）
{
free（（*S）.base）;
（*S）.base=NULL;
（*S）.top=NULL;
（*S）.stacksize=0;
returnOK;
}
StatusStackEmpty（SqStack*S）
{
if（（*S）.top==（*S）.base）returnOK;
elsereturnERROR;
}
StatusPush（SqStack*S,SElemTypee）//插入元素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;
returnOK;
}
StatusPop（SqStack*S,SElemType*e）
{
if（（*S）.top==（*S）.base）returnERROR;
*e=*--S->top;
returnOK;
}
intTransfor（charc）
{//返回字符c在优先关系表中的序号
intk;
switch（c）
{case'+':
k=0;break;
case'-':
k=1;break;
case'*':
k=2;break;
case'/':
k=3;break;
case'（':
k=4;break;
case'）':
k=5;break;
case'#':
k=6;break;
}
returnk;
}
charPrecede（charc1,charc2）
{//判断c1与c2的位序关系,
chara[7][7]={
/*运算符之间的优先级制作成一张表格*/
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'},
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='}};
i=Transfor（c1）;
j=Transfor（c2）;
return（a[i][j]）;
}
StatusIn（charc,charOP[]）
{//判断字符c是否为运算符
inti;
for（i=0;i<=6;i++）
if（c==OP[i]）returnTRUE;
returnFALSE;
}
charOperate（chara,SElemTypetheta,charb）
{//数值计算
intz;
switch（theta）
{case'+':
z=a+b;break;
case'-':
z=b-a;break;
case'*':
z=a*b;break;
case'/':
z=b/a;break;
}
returnz;
}
SElemTypeGetTop（SqStack*S）
{//若栈不空,用e返回栈顶元素并返回OK,否则返回ERROR
SElemTypee;
if（（*S）.top==（*S）.base）returnERROR;
e=*（（*S）.top-1）;
returne;
}
main（）
{SElemTypec,elem;//运算符
SqStackOPTR,OPND;//运算符栈和运算数栈
inta,b,thera;//运算数
charOP[7]={'+','-','*','/','（','）','#'};
InitStack（&OPTR）;InitStack（&OPND）;
Push（&OPTR,'#'）;
printf（"请输入正确的算数表达式，并以#结束\n"）;
c=getchar（）;
elem=GetTop（&OPND）;
while（c!
='#'||GetTop（&OPTR）!
='#'）
{if（!
In（c,OP））{Push（&OPND,c）;
c=getchar（）;
}//不是运算符则进栈
else
{if（c=='-'）
Push（&OPND,0）;
switch（Precede（GetTop（&OPTR）,c））
{case'<':
//栈顶元素优先权低
Push（&OPTR,c）;c=getchar（）;
break;
case'=':
//脱括号并接受下一个字符
Pop（&OPTR,&elem）;c=getchar（）;
break;
case'>':
//退栈并将运算结果入栈
Pop（&OPTR,&elem）;thera=elem;
Pop（&OPND,&elem）;a=elem;
Pop（&OPND,&elem）;b=elem;
Push（&OPND,Operate（a,thera,b））;
break;
}//switch
}
}
printf（"计算结果是:
%d\n",GetTop（&OPND））;
}
升级会员 