大数据结构实习报告材料设计一个演示用运算优先法对算数表达式求值过程地程序.docx
《大数据结构实习报告材料设计一个演示用运算优先法对算数表达式求值过程地程序.docx》由会员分享，可在线阅读，更多相关《大数据结构实习报告材料设计一个演示用运算优先法对算数表达式求值过程地程序.docx（18页珍藏版）》请在冰点文库上搜索。
大数据结构实习报告材料设计一个演示用运算优先法对算数表达式求值过程地程序
实习报告
题目：
设计一个演示用运算优先法对算数表达式求值过程的程序。
班级：
姓名：
学号：
完成日期：
一、需求分析
1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.
2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；括号（（））），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。
3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。
4测试数据见原题。
5程序执行的命令包括：
（1）建立算数表达式；
（2）得到运算表达式的值；
（3）演示运算过程。
二、概要设计
1.设定栈的抽象数据类型定义：
ADTStack{
数据对象
D＝{ai|ai∈charSet,i=1,2,...,n,n≥0}
数据关系：
R1＝{|ai-1,ai∈D,i=2,...,n}
（约定an端为栈顶，a1端为栈底）
基本操作：
InitStack（&S）
操作结果：
构造一个空栈S。
Gettop（S,&e）
初始条件：
栈S已存在。
操作结果：
若栈S不空，则以e返回栈顶元素。
Push（&S,e）
初始条件：
栈S已存在。
操作结果：
插入元素e为新的栈顶元素。
Pop（&S,&e）
初始条件：
栈S已存在且非空。
操作结果：
删除S的栈顶元素，并用e返回其值。
}ADTStack
2.本程序包括三个模块
（1）主程序模块：
Voidmain（）
{
初始化；
函数；
}
（2）栈模块——实现栈抽象数据类型
（3）运算模块——实现运算并演示其过程模块
各模块之间调用关系如下：
主程序模块
运算模块
栈模块
三、详细设计
1、元素类型、结点类型
typedefstruct{
int*base;
int*top;
intstacksize;
}SqStack1;//操作数栈
typedefstruct{
char*base;
char*top;
intstacksize;
}SqStack2;//操作符栈
2、栈类型
typedefstruct{
char*base;
char*top;
intstacksize;
}Stack; //栈类型
栈的基本操作设置如下：
voidInitStack（Stack&S）
//初始化，设S为空栈（S.top=NULL）
StatusGetTop（StackS,ElemTypee）
//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE
StatusPush（Stack&S,ElemTypee）
//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，
//否则返回FALSE其中部分操作的算法：
StatusPush（Stack&S,ElemTypee）
{
//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；
//否则栈不变，并返回FALSE
if（MakeNode（p,e））{
P.next=S.top;S.top=p;
S.size++;
ReturnTRUE;
}
elsereturnFALSE;
}
StatusPop（Stack&S,ElemType&e）
{
//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，
//否则返回FALSE，且e无意义
if（StackEmpty（S））returnFALSE;
else{
p=S.top;S.top=S.top->next;
e=p->:
data;S.size--;
returnTRUE;
}
}
3、运算代码
intOperate（inta,chartheta,intb）//计算表达式值：
主要是将大的表达式转化成小的表达式进行逐步求值
{
intc;
if（theta=='+'）c=a+b;
elseif（theta=='-'）c=a-b;
elseif（theta=='*'）c=a*b;
elsec=a/b;
returnc;
}//Operate
intresult（SqStack1*OPND,SqStack2*OPTR）//求值
{
chara=0;
chartheta;
intb,c,number=0;
IntInitStack（OPND）;
CharInitStack（OPTR）;
CharPush（OPTR,'#'）;
a=getchar（）;
while（a!
='#'||CharGetTop（OPTR）!
='#'）
{
printf（"输入字符：
%c",a）;
if（!
In（a））//不是运算符则进栈
{
number=0;
while（!
In（a））
{
number=number*10+（a-48）;//处理多位整数z=10*x+y
a=getchar（）;
}
IntPush（OPND,number）;
printf（"主要操作：
Push（OPND,%d）",number）;
}
else
switch（Precede（a,CharGetTop（OPTR）））
{
case'<':
CharPush（OPTR,a）;
a=getchar（）;
printf（"主要操作：
Push（OPTR,%c）",a）;
break;
case'=':
CharPop（OPTR）;
a=getchar（）;
printf（"主要操作：
Pop（OPTR,%c）",a）;
break;
case'>':
theta=CharPop（OPTR）;
c=IntPop（OPND）;
b=IntPop（OPND）;
IntPush（OPND,Operate（b,theta,c））;
printf（"主要操作：
Operate（%d,%c,%d）",b,theta,c）;
break;
}
printf（"OPND栈：
%dOPTR栈：
%c\n",IntGetTop（OPND）,CharGetTop（OPTR））;
}
printf（"Theresultis%d.\n",IntGetTop（OPND））;//打印输出表达式值
returnOK;
}
4.主函数和其他函数的代码
voidmain（）//主函数，使用自定义函数完成功能
{
SqStack1s1,*OPND;
SqStack2s2,*OPTR;
OPND=&s1;
OPTR=&s2;
printf（"Pleaseenteranexpressionwithaendof'#'.\n"）;
printf（"TheExpression:
"）;
result（OPND,OPTR）;
}
charPrecede（chara,charb）//运算优先级判断
{
inti,j;
charTable[8][8]={
'','+','-','*','/','（','）','#',
'+','>','>','<','<','<','>','>',
'-','>','>','<','<','<','>','>',
'*','>','>','>','>','<','>','>',
'/','>','>','>','>','<','>','>',
'（','<','<','<','<','<','=','',
'）','>','>','>','>','','>','>',
'#','<','<','<','<','<','','=',
};//优先级表格
for（i=0;i<8;i++）
if（Table[0][i]==a）//纵坐标寻找
break;
for（j=0;j<8;j++）//横坐标寻找
if（Table[j][0]==b）
break;
returnTable[j][i];
}
intIn（charc）//判断c是否为操作符
{
if（c=='（'||c=='+'||c=='-'||c=='*'||c=='/'||c=='）'||c=='#'||c=='^'）
return1;//如果是操作符返回1
else
return0;//不是，返回0
}
5．函数的调用关系图反映了演示程序的层次结构：
四、调试分析
算术表达式求值程序较为庞大，调试花费时间较多，主要是在for循环和while循环时容易出错，对于涉及的循环的操作开始和结束条件设置很关键。
五、用户手册
1.本程序开发环境为VC6.0，运行环境为dos操作系统，执行文件为：
1.exe
2.运行该程序后,产生如下图所示的界面：
3.按照提示输入一组表达式。
4.输入完成后，按回车键。
5.屏幕上打印出对应于该表达式的后缀表达式。
6.打印表达式计算结果。
六、测试结果
1.
2.
3
4.
七、附录
源程序文件名清单：
1.cpp//主程序
1.exe//可执行文件
stdio.h//程序中用到的头文件
stdlib.h//程序中用到的头文件
string.h//程序中用到的头文件
math.h//程序中用到的头文件
程序代码：
：
#include
#include
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineERROR0
#defineOK1
//********************************************栈模块
typedefstructSqStack1//运算数栈
{
int*base;
int*top;
intstacksize;
}SqStack1;
typedefstructSqStack2//运算符栈
{
char*base;
char*top;
intstacksize;
}SqStack2;
voidIntInitStack（SqStack1*S）
{
S->base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
if（!
S->base）exit（ERROR）;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
voidCharInitStack（SqStack2*S）
{
S->base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;
if（!
S->base）exit（ERROR）;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
intIntGetTop（SqStack1*S）//取栈顶元素
{
inte;
if（（*S）.top==（*S）.base）
return0;
e=*（（*S）.top-1）;
returne;
}
charCharGetTop（SqStack2*S）//取栈顶元素
{
chare;
if（（*S）.top==（*S）.base）return0;
e=*（（*S）.top-1）;
returne;
}
intIntPush（SqStack1*S,inte）
{
*（*S）.top++=e;
returnOK;
}
intCharPush（SqStack2*S,chare）
{
*（*S）.top++=e;
returnOK;
}
intIntPop（SqStack1*S）
{
inte;
if（（*S）.top==（*S）.base）return0;
e=*--（*S）.top;
returne;
}
intCharPop（SqStack2*S）
{
chare;
if（（*S）.top==（*S）.base）return0;
e=*--（*S）.top;
returne;
}
//——————————————————*******************运算模块
charPrecede（chara,charb）//运算优先级判断
{
inti,j;
charTable[8][8]={
'','+','-','*','/','（','）','#',
'+','>','>','<','<','<','>','>',
'-','>','>','<','<','<','>','>',
'*','>','>','>','>','<','>','>',
'/','>','>','>','>','<','>','>',
'（','<','<','<','<','<','=','',
'）','>','>','>','>','','>','>',
'#','<','<','<','<','<','','=',
};//优先级表格
for（i=0;i<8;i++）
if（Table[0][i]==a）//纵坐标寻找
break;
for（j=0;j<8;j++）//横坐标寻找
if（Table[j][0]==b）
break;
returnTable[j][i];
}
intOperate（inta,chartheta,intb）//计算表达式值：
主要是将大的表达式转化成小的表达式进行逐步求值
{
intc;
if（theta=='+'）c=a+b;
elseif（theta=='-'）c=a-b;
elseif（theta=='*'）c=a*b;
elsec=a/b;
returnc;
}//Operate
intIn（charc）//判断c是否为操作符
{
if（c=='（'||c=='+'||c=='-'||c=='*'||c=='/'||c=='）'||c=='#'||c=='^'）
return1;//如果是操作符返回1
else
return0;//不是，返回0
}
intresult（SqStack1*OPND,SqStack2*OPTR）//求值
{
chara=0;
chartheta;
intb,c,number=0;
IntInitStack（OPND）;
CharInitStack（OPTR）;
CharPush（OPTR,'#'）;
a=getchar（）;
while（a!
='#'||CharGetTop（OPTR）!
='#'）
{
printf（"输入字符：
%c",a）;
if（!
In（a））//不是运算符则进栈
{
number=0;
while（!
In（a））
{
number=number*10+（a-48）;//处理多位整数z=10*x+y
a=getchar（）;
}
IntPush（OPND,number）;
printf（"主要操作：
Push（OPND,%d）",number）;
}
else
switch（Precede（a,CharGetTop（OPTR）））
{
case'<':
CharPush（OPTR,a）;
a=getchar（）;
printf（"主要操作：
Push（OPTR,%c）",a）;
break;
case'=':
CharPop（OPTR）;
a=getchar（）;
printf（"主要操作：
Pop（OPTR,%c）",a）;
break;
case'>':
theta=CharPop（OPTR）;
c=IntPop（OPND）;
b=IntPop（OPND）;
IntPush（OPND,Operate（b,theta,c））;
printf（"主要操作：
Operate（%d,%c,%d）",b,theta,c）;
break;
}
printf（"OPND栈：
%dOPTR栈：
%c\n",IntGetTop（OPND）,CharGetTop（OPTR））;
}
printf（"\n结果:
%d.\n",IntGetTop（OPND））;//打印输出表达式值
returnOK;
}
//————————————————————————主程序模块
voidmain（）//主函数，使用自定义函数完成功能
{
SqStack1s1,*OPND;
SqStack2s2,*OPTR;
OPND=&s1;
OPTR=&s2;
printf（"请输入算数表达式并以'#'结尾.\n"）;
printf（"算数表达式:
"）;
result（OPND,OPTR）;
}
升级会员 