北理工自动化数据结构实验报告2.docx
《北理工自动化数据结构实验报告2.docx》由会员分享，可在线阅读，更多相关《北理工自动化数据结构实验报告2.docx（21页珍藏版）》请在冰点文库上搜索。
北理工自动化数据结构实验报告2
《数据结构与算法设计》
实验报告
——实验二
一、实验目的
按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
二、实验内容
简单计算器。
请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
要求：
1从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。
2输入表达式中的数值均为大于等于零的整数。
中间的计算过程如果出现小数也只取整。
例如，输入：
4+2*5=输出：
14
输入：
（4+2）*（2-10）=输出：
-48
三、程序设计
概要设计
1、宏定义
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
2、基本函数：
（1）voidInitStack_char（SqStack*S）
char型栈初始化
（2）voidInitStack_int（sqStack*S）
int型栈初始化
（3）voidPush_char（SqStack*S,charch）
char型元素进栈
（4）voidPush_int（sqStack*S,intnum）
int型元素进栈
（5）charGetTop_char（SqStack*S）
取char型栈顶元素
（6）intGetTop_int（sqStack*S）
取int型栈顶元素
（7）StatusIn（charc）
判断是否为运算符，若是运算符则返回，否则返回
（8）charPrecede（chara,charb）
判断两运算符的先后次序
（9）StatusPop_char（SqStack*S,char&x）
char型栈出栈
（10）StatusPop_int（sqStack*S,int&x）
int型栈出栈
（11）intOperate（inta,chartheta,intb）
计算a和b运算结果
3、主要流程
由主程序首先调用InPut（L）函数创建顺序表，调用InsertSort（L）函数进行插入排序，调用OutPut（L）函数显示排序结果。
再由主程序首先调用InPut（L）函数创建顺序表，调用QuickSort（L）函数进行交换排序，调用OutPut（L）函数显示排序结果。
再由主程序首先调用InPut（L）函数创建顺序表，调用SelectSort（L）函数进行选择排序，调用OutPut（L）函数显示排序结果。
4、模块调用关系
由主函数模块调用创建顺序表模块，排序模块与显示输出模块。
3、流程图
Y
N
Y
N
4、详细设计
数据类型
typedefstructnode//构造char型栈
{
charch;
structnode*next;
}node;
typedefstruct
{
structnode*base;
structnode*top;
}SqStack;
typedefstructlnode//构造int型栈
{
intnum;
structlnode*next;
}lnode;
typedefstruct
{
structlnode*base;
structlnode*top;
}sqStack;
操作部分
voidInitStack_char（SqStack*S）
{
S->base=（node*）malloc（sizeof（node））;
S->base->next=NULL;
S->top=S->base;
}//char型栈初始化
voidInitStack_int（sqStack*S）
{
S->base=（lnode*）malloc（sizeof（lnode））;
S->base->next=NULL;
S->top=S->base;
}//int型栈初始化
voidPush_char（SqStack*S,charch）
{
node*p;
p=（node*）malloc（sizeof（node））;
p->ch=ch;
p->next=S->top;
S->top=p;
}//char型元素进栈
StatusPush_int（sqStack*S,intnum）
{
lnode*p;
p=（lnode*）malloc（sizeof（lnode））;
p->num=num;
p->next=S->top;
S->top=p;
returnOK;
}//int型元素进栈
charGetTop_char（SqStack*S）
{
return（S->top->ch）;
}//取char型栈顶元素
intGetTop_int（sqStack*S）
{
return（S->top->num）;
}//取int型栈顶元素
StatusPop_char（SqStack*S,char&x）
{
if（S->base==S->top）
returnERROR;
node*p;
p=S->top;
x=p->ch;
S->top=p->next;
free（p）;
returnOK;
}//char型栈出栈
StatusPop_int（sqStack*S,int&x）
{
if（S->base==S->top）
returnERROR;
lnode*p;
p=S->top;
x=p->num;
S->top=p->next;
free（p）;
returnOK;
}//int型栈出栈
计算功能
intOperate（inta,chartheta,intb）
{
inti,z=1;
switch（theta）
{
case'+':
z=（a+b）;break;
case'-':
z=（a-b）;break;
case'*':
z=（a*b）;break;
case'/':
z=（a/b）;break;
case'^':
for（i=1;i<=b;i++）
z=z*a;
break;
}
return（z）;
}//计算a和b运算结果
StatusIn（charc）
{
if（c=='+'||c=='-'||c=='*'||c=='/'||c=='（'||c=='）'||c=='='||c=='^'）
returnOK;
else
returnERROR;
}//判断是否为运算符
charPrecede（chara,charb）
{
if（a=='+'||a=='-'）
{
if（b=='+'||b=='-'||b=='）'||b=='='）
return'>';
else
return'<';
}
if（a=='*'||a=='/'）
{
if（b=='（'||b=='^'）
return'<';
else
return'>';
}
if（a=='（'）
{
if（b=='）'）
return'=';
else
return'<';
}
if（a=='）'）
{
if（b!
='（'）
return'>';
}
if（a=='#'）
{
if（b=='='）
return'=';
else
return'<';
}
if（a=='^'）
return（'>'）;
}//判断两运算符的先后次序
主函数
intmain（）//主函数
{
charc,x,theta;
inta,b,c1;//定义变量
SqStackOPTR;//定义字符栈
sqStackOPNR;//定义整型栈
InitStack_char（&OPTR）;//初始化
InitStack_int（&OPNR）;//初始化
Push_char（&OPTR,'#'）;//将字符型栈底设为#
c=getchar（）;//从键盘输入得到字符
while（c!
='='||GetTop_char（&OPTR）!
='#'）//判定是否执行循环
{
if（!
In（c））
{
c1=0;
while（!
In（c））
{
c1=c1*10+c-'0';
c=getchar（）;
}
Push_int（&OPNR,c1）;
}//当扫描字符不是运算符时，转化为整型数存入栈中
else
{
switch（Precede（GetTop_char（&OPTR）,c））//判定运算符的优先关系
{
case'<':
Push_char（&OPTR,c）;c=getchar（）;break;//当前运算符优先级高，存入char栈
case'=':
Pop_char（&OPTR,c）;c=getchar（）;break;//运算符次序相等，存入char栈
case'>':
//当前运算符优先级低
Pop_char（&OPTR,theta）;
Pop_int（&OPNR,b）;
Pop_int（&OPNR,a）;
Push_int（&OPNR,Operate（a,theta,b））;//计算运算结果，并存入int栈
break;//继续循环
}
}
}
printf（"%d\n",GetTop_int（&OPNR））;//计算完成，取出int栈顶元素，并输出
return0;
}
四、程序调试分析
编写程序的过程中遇到了很多的问题，比如开始时，使用getchar函数输入，但其有较大的弊端，只能输入0-9之间的整数，不能实现多位数及小数的计算。
于是换为gets函数，将表达式作为整体存入数组中待处理，在后续程序中加以转换。
还有，在设计主要处理函数时，出现了多次编译错误。
最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error。
还有许多问题后发现是由于指针指向混乱造成。
这主要是自己的思路不清并且混淆了部分函数，导致程序结构混乱。
后来仔细绘制了流程图，详尽的分析了过程后，在课本和网上资料的辅助下，终于成功的解决了该问题。
这也说明编程需要细心和耐心，只有一步一步的编写，不断的调试和修改，才能最终得到想要的结果。
五、用户使用说明
1.本程序的运行环境为Windows操作系统下的MicrosoftVisualC++6.0。
2.在VC环境下打开程序后，点击运行。
3.从键盘输入一个完整的表达式，以“=”作为表达式输入结束的标志，按回车键即可得到结果。
六、程序运行结果
（1）输入：
4+2*5=输出：
14
（2）输入：
（4+2）*（2-10）=输出：
-48
（3）输入：
3*（4+1）=输出：
15
七、程序清单
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
typedefintStatus;
typedefstructnode
//构造char型栈
{
charch;
structnode*next;
}node;
typedefstruct
{
structnode*base;
structnode*top;
}SqStack;
typedefstructlnode
//构造int型栈
{
intnum;
structlnode*next;
}lnode;
typedefstruct
{
structlnode*base;
structlnode*top;
}sqStack;
voidInitStack_char（SqStack*S）
{
S->base=（node*）malloc（sizeof（node））;
S->base->next=NULL;
S->top=S->base;
}
//char型栈初始化
voidInitStack_int（sqStack*S）
{
S->base=（lnode*）malloc（sizeof（lnode））;
S->base->next=NULL;
S->top=S->base;
}
//int型栈初始化
voidPush_char（SqStack*S,charch）
{
node*p;
p=（node*）malloc（sizeof（node））;
p->ch=ch;
p->next=S->top;
S->top=p;
}
//char型元素进栈
StatusPush_int（sqStack*S,intnum）
{
lnode*p;
p=（lnode*）malloc（sizeof（lnode））;
p->num=num;
p->next=S->top;
S->top=p;
returnOK;
}
//int型元素进栈
charGetTop_char（SqStack*S）
{
return（S->top->ch）;
}
//取char型栈顶元素
intGetTop_int（sqStack*S）
{
return（S->top->num）;
}
//取int型栈顶元素
StatusPop_char（SqStack*S,char&x）
{
if（S->base==S->top）
returnERROR;
node*p;
p=S->top;
x=p->ch;
S->top=p->next;
free（p）;
returnOK;
}
//char型栈出栈
StatusPop_int（sqStack*S,int&x）
{
if（S->base==S->top）
returnERROR;
lnode*p;
p=S->top;
x=p->num;
S->top=p->next;
free（p）;
returnOK;
}
//int型栈出栈
intOperate（inta,chartheta,intb）
{
inti,z=1;
switch（theta）
{
case'+':
z=（a+b）;break;
case'-':
z=（a-b）;break;
case'*':
z=（a*b）;break;
case'/':
z=（a/b）;break;
case'^':
for（i=1;i<=b;i++）
z=z*a;
break;
}
return（z）;
}
//计算a和b运算结果
StatusIn（charc）
{
if（c=='+'||c=='-'||c=='*'||c=='/'||c=='（'||c=='）'||c=='='||c=='^'）
returnOK;
else
returnERROR;
}
//判断是否为运算符
charPrecede（chara,charb）
{
if（a=='+'||a=='-'）
{
if（b=='+'||b=='-'||b=='）'||b=='='）
return'>';
else
return'<';
}
if（a=='*'||a=='/'）
{
if（b=='（'||b=='^'）
return'<';
else
return'>';
}
if（a=='（'）
{
if（b=='）'）
return'=';
else
return'<';
}
if（a=='）'）
{
if（b!
='（'）
return'>';
}
if（a=='#'）
{
if（b=='='）
return'=';
else
return'<';
}
if（a=='^'）
return（'>'）;
}
//判断两运算符的先后次序
intmain（）
//主函数
{
charc,x,theta;
inta,b,c1;//定义变量
SqStackOPTR;//定义字符栈
sqStackOPNR;//定义整型栈
InitStack_char（&OPTR）;//初始化
InitStack_int（&OPNR）;//初始化
Push_char（&OPTR,'#'）;//将字符型栈底设为#
c=getchar（）;//从键盘输入得到字符
while（c!
='='||GetTop_char（&OPTR）!
='#'）//判定是否执行循环
{
if（!
In（c））
{
c1=0;
while（!
In（c））
{
c1=c1*10+c-'0';
c=getchar（）;
}
Push_int（&OPNR,c1）;
}
//当扫描字符不是运算符时，转化为整型数存入栈中
else
{
switch（Precede（GetTop_char（&OPTR）,c））//判定运算符的优先关系
{
case'<':
Push_char（&OPTR,c）;c=getchar（）;break;
//当前运算符优先级高，存入char栈
case'=':
Pop_char（&OPTR,c）;c=getchar（）;break;
//运算符次序相等，存入char栈
case'>':
//当前运算符优先级低
Pop_char（&OPTR,theta）;
Pop_int（&OPNR,b）;
Pop_int（&OPNR,a）;
Push_int（&OPNR,Operate（a,theta,b））;//计算运算结果，并存入int栈
break;//继续循环
}
}
}
printf（"%d\n",GetTop_int（&OPNR））;
//计算完成，取出int栈顶元素，并输出
return0;
}
升级会员 