北理工数据结构实验报告.docx
《北理工数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《北理工数据结构实验报告.docx（19页珍藏版）》请在冰点文库上搜索。
北理工数据结构实验报告
《数据结构与算法设计》
实验报告
——实验二
学院：
自动化学院
班级：
____
学号：
__
姓名：
_____
一、实验目的
1、熟悉VC环境，学习使用C语言实现栈的存储结构。
2、通过编程、上机调试，进一步理解栈的基本概念。
3、锻炼动手编程，独立思考的能力。
二、实验内容
实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
要求支持运算符：
+、-、*、/、%、（）和=：
①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；
②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。
例如，输入：
4+2*5=输出：
14
输入：
（4+2）*（2-10）=输出：
-48
三、程序设计
1、概要设计
为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。
为此，需要栈的抽象数据结构。
（1）、栈的抽象数据类型定义为：
ADTStack{
数据对象：
D=
数据关系：
R1=
约定
端为栈顶，
端为栈底。
基本操作：
InitStack（&S）
操作结果：
创建一个空栈S。
GetTop（S,&e）
初始条件：
栈S已存在且非空。
操作结果：
用e返回S的栈顶元素。
Push（&S,e）
初始条件：
栈S已存在。
操作结果：
插入元素e为新的栈顶元素。
Pop（&S,&e）
初始条件：
栈S已存在且非空。
操作结果：
删除S的栈顶元素，并用e返回其值。
In（m,a[]）
操作结果：
若m是运算符，返回TRUE。
Precede（m,n）
初始条件：
m，n为运算符。
操作结果：
若m优先级大于n，返回>，反之亦然。
Operation（a,theta,b）
初始条件：
a，b为整数，theta为运算符。
操作结果：
返回a与b运算的结果。
EvaluateExpression（p[]）
初始条件：
输入合法的表达式。
操作结果：
返回表达式的值。
}ADTStack
（2）、宏定义
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineOVERFLOW-2
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
（3）、主程序流程
首先定义char型数组，将输入的表达式存入。
随后调用EvaluateExpression（expression）函数计算结果，最后输出在屏幕上。
（4）、模块调用关系：
由主函数模块调用输入模块与求值模块。
求值模块调用表达式转化模块与表达式求职模块，计算并返回表达式的值。
最后主程序调用输出模块输出结果。
（5）、流程图
开始
输入表达式
charc=表达式首字符
c!
='='||GetTop1（OPTR）!
='='
!
In（c,OP）
c存入数组;c=*（++ex）;
In（c,OP）
数组中的数压入栈内;指针指向数组首元素
case'<':
符号进栈c=*（++ex）;
case'=':
符号出栈c=*（++ex）;
case'>':
操作数栈前2个数运算
returnGetTop2（OPND）
输出result
结束
2、详细设计
（1）、数据类型设计
typedefstruct{
char*base;
char*top;
intstacksize;
}SqStack1;//定义运算符栈数据类型
typedefstruct{
int*base;
int*top;
intstacksize;
}SqStack2;//定义操作数栈数据类型
SqStack1OPTR;//声明运算符栈
SqStack2OPND;//声明操作数栈
（2）、操作算法设计
StatusInitStack1（SqStack1&S）{
//构造运算符栈
S.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;
//申请空间
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//InitStack1
StatusInitStack2（SqStack2&S）{
//构造操作数栈
S.base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
//申请空间
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//InitStack2
charGetTop1（SqStack1S）{
//取得运算符栈的栈顶元素
chare;
if（S.top==S.base）returnERROR;//栈空
e=*（S.top-1）;
returne;
}//GetTop1
intGetTop2（SqStack2S）{
//取得操作数栈的栈顶元素
inte;
if（S.top==S.base）returnERROR;//栈空
e=*（S.top-1）;
returne;
}//GetTop2
StatusPush1（SqStack1&S,chare）{
//插入元素e为运算符栈的栈顶元素
if（S.top-S.base>=S.stacksize）{//栈满，追加存储空间
S.base=（char*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（char））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}//Push1
StatusPush2（SqStack2&S,inte）{
//插入元素e为操作数栈的栈顶元素
if（S.top-S.base>=S.stacksize）{//栈满，追加存储空间
S.base=（int*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（int））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}//Push2
StatusPop1（SqStack1&S,char&e）{
//删除表达式栈的栈顶元素并用e返回
if（S.top==S.base）returnERROR;//栈空
e=*--S.top;
returnOK;
}//Pop1
StatusPop2（SqStack2&S,int&e）{
//删除表达式栈的栈顶元素并用e返回
if（S.top==S.base）returnERROR;//栈空
e=*--S.top;
returnOK;
}//Pop2
StatusIn（intm,chara[]）{
//判断m若是运算符，返回TRUE，否则返回FALSE
for（intn=0;a[n]!
='\0';n++）
if（m==a[n]）returnTRUE;
returnFALSE;
}//In
charPrecede（charm,charn）{
//判断m与n的优先级
switch（m）{
case'+':
case'-':
if（n=='+'||n=='-'||n=='）'||n=='='）
return'>';
elsereturn'<';break;
case'*':
case'/':
case'^':
case'%':
if（n=='（'）
return'<';
elsereturn'>';break;
case'（':
if（n=='）'）
return'=';
elseif（n=='='）
returnERROR;
elsereturn'<';break;
case'）':
if（n=='（'）
returnERROR;
elsereturn'>';break;
case'=':
if（n=='='）
return'=';
elseif（n=='）'）
returnERROR;
elsereturn'<';break;
default:
returnERROR;break;//其他情况，表达式有误
}
}//Precede
intOperation（inta,chartheta,intb）{
//运算函数
switch（theta）{
case'+':
returna+b;break;
case'-':
returna-b;break;
case'*':
returna*b;break;
case'/':
returna/b;break;
case'%':
returna%b;break;
case'^':
returnpow（a,b）;break;
default:
returnERROR;break;
}
}//Operation
intEvaluateExpression（charp[]）{
//主要操作函数
inta,b,t;charx,theta,temp[10];
char*num=temp;char*ex=p;//声明指针
InitStack1（OPTR）;Push1（OPTR,'='）;
InitStack2（OPND）;charc=*p;
while（c!
='='||GetTop1（OPTR）!
='='）{
if（!
In（c,OP））{//不是运算符进数组
*（num++）=c;c=*（++ex）;
if（In（c,OP））{//是运算符将数组压入栈
*num='\0';
t=atoi（temp）;//将temp数组转化为整型数
num=temp;//指针指回数组头元素
Push2（OPND,t）;
}
}
else
switch（Precede（GetTop1（OPTR）,c））{
case'<':
//栈顶元素优先级低
Push1（OPTR,c）;c=*（++ex）;
break;
case'=':
//脱括号并接受下一字符
Pop1（OPTR,x）;c=*（++ex）;
break;
case'>':
//运算并将结果入栈
Pop1（OPTR,theta）;
Pop2（OPND,b）;Pop2（OPND,a）;
Push2（OPND,Operation（a,theta,b））;
break;
}
}
returnGetTop2（OPND）;返回操作数栈顶元素
}//EvaluateExpression
（3）、主函数设计
intmain（）{
//主函数
intresult;charexpression[100];//声明表达式数组
printf（"Pleaseinputtheexpression:
"）;
gets（expression）;//输入数组
result=EvaluateExpression（expression）;
printf（"theresultis:
%d\n",result）;//输出结果
return0;
}
四、程序调试分析
1、开始时，使用getchar函数输入，但其有较大的弊端，只能输入0-9之间的整数，不能实现多位数及小数的计算。
于是换为gets函数，将表达式作为整体存入数组中待处理。
2、第一个问题解决后，出现了第二个问题：
数据结构混乱。
由于gets函数得到的是char型，直接存入操作数栈后，以ASCII码形式存入，使得编译通过但运行结果错误。
后来分析原因后，引入暂存数组，利用atoi函数，将数组中的数转化为整型，解决了这一问题。
3、在设计主要处理函数时，出现了多次编译错误。
后发现是由于指针指向混乱造成。
这主要是自己的思路不清，导致程序混乱。
后仔细绘制了流程图，详尽的分析了过程后，解决了该问题。
五、用户使用说明
1、本程序的运行环境为DOS操作系统，执行文件为：
Josegh.exe。
2、进入程序后，在Pleaseinputtheexpression:
后输入待求表达式，以“=”结尾，并敲回车。
3、程序运行后即在屏幕上输出计算结果。
六、程序运行结果
1、
2、
七、程序清单
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineOVERFLOW-2
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#include"stdio.h"
#include"stdlib.h"
#include"math.h"
typedefintStatus;
charOP[]={'+','-','*','/','（','）','^','%','='};//定义运算符数组
typedefstruct{
char*base;
char*top;
intstacksize;
}SqStack1;//定义运算符栈数据类型
typedefstruct{
int*base;
int*top;
intstacksize;
}SqStack2;//定义操作数栈数据类型
SqStack1OPTR;//声明运算符栈
SqStack2OPND;//声明操作数栈
StatusInitStack1（SqStack1&S）{
//构造运算符栈
S.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;
//申请空间
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusInitStack2（SqStack2&S）{
//构造操作数栈
S.base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
//申请空间
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
charGetTop1（SqStack1S）{
//取得运算符栈的栈顶元素
chare;
if（S.top==S.base）returnERROR;//栈空
e=*（S.top-1）;
returne;
}
intGetTop2（SqStack2S）{
//取得操作数栈的栈顶元素
inte;
if（S.top==S.base）returnERROR;//栈空
e=*（S.top-1）;
returne;
}
StatusPush1（SqStack1&S,chare）{
//插入元素e为运算符栈的栈顶元素
if（S.top-S.base>=S.stacksize）{//栈满，追加存储空间
S.base=（char*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（char））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPush2（SqStack2&S,inte）{
//插入元素e为操作数栈的栈顶元素
if（S.top-S.base>=S.stacksize）{//栈满，追加存储空间
S.base=（int*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（int））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPop1（SqStack1&S,char&e）{
//删除表达式栈的栈顶元素并用e返回
if（S.top==S.base）returnERROR;//栈空
e=*--S.top;
returnOK;
}
StatusPop2（SqStack2&S,int&e）{
//删除表达式栈的栈顶元素并用e返回
if（S.top==S.base）returnERROR;//栈空
e=*--S.top;
returnOK;
}
StatusIn（intm,chara[]）{
//判断m若是运算符，返回TRUE，否则返回FALSE
for（intn=0;a[n]!
='\0';n++）
if（m==a[n]）returnTRUE;
returnFALSE;
}
charPrecede（charm,charn）{
//判断m与n的优先级
switch（m）{
case'+':
case'-':
if（n=='+'||n=='-'||n=='）'||n=='='）
return'>';
elsereturn'<';break;
case'*':
case'/':
case'^':
case'%':
if（n=='（'）
return'<';
elsereturn'>';break;
case'（':
if（n=='）'）
return'=';
elseif（n=='='）
returnERROR;
elsereturn'<';break;
case'）':
if（n=='（'）
returnERROR;
elsereturn'>';break;
case'=':
if（n=='='）
return'=';
elseif（n=='）'）
returnERROR;
elsereturn'<';break;
default:
returnERROR;break;//其他情况，表达式有误
}
}
intOperation（inta,chartheta,intb）{
//运算函数
switch（theta）{
case'+':
returna+b;break;
case'-':
returna-b;break;
case'*':
returna*b;break;
case'/':
returna/b;break;
case'%':
returna%b;break;
case'^':
returnpow（a,b）;break;
default:
returnERROR;break;
}
}
intEvaluateExpression（charp[]）{
//主要操作函数
inta,b,t;charx,theta,temp[10];
char*num=temp;char*ex=p;//声明指针
InitStack1（OPTR）;Push1（OPTR,'='）;
InitStack2（OPND）;charc=*p;
while（c!
='='||GetTop1（OPTR）!
='='）{
if（!
In（c,OP））{//不是运算符进数组
*（num++）=c;c=*（++ex）;
if（In（c,OP））{//是运算符将数组压入栈
*num='\0';
t=atoi（temp）;//将temp数组转化为整型数
num=temp;//指针指回数组头元素
Push2（OPND,t）;
}
}
else
switch（Precede（GetTop1（OPTR）,c））{
case'<':
//栈顶元素优先级低
Push1（OPTR,c）;c=*（++ex）;
break;
case'=':
//脱括号并接受下一字符
Pop1（OPTR,x）;c=*（++ex）;
break;
case'>':
//运算并将结果入栈
Pop1（OPTR,theta）;
Pop2（OPND,b）;Pop2（OPND,a）;
Push2（OPND,Operation（a,theta,b））;
break;
}
}
returnGetTop2（OPND）;返回操作数栈顶元素
}
intmain（）{
//主函数
intresult;charexpression[100];//声明表达式数组
printf（"Pleaseinputtheexpression:
"）;
gets（expression）;//输入数组
result=EvaluateExpression（expression）;
printf（"theresultis:
%d\n",result）;//输出结果
return0;
}
升级会员 