数据结构实验报告 表达式求值.docx
- 文档编号:3170908
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:22
- 大小:40.46KB
数据结构实验报告 表达式求值.docx
《数据结构实验报告 表达式求值.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告 表达式求值.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构实验报告表达式求值
(一)需求分析
1、输入的形式和输入值的范围:
根据题目要求与提示,先选择你要使用的表达式形式(中缀用1,后缀用0),在输入一个中缀表达式,输入数的范围为int型,此时,程序将计算出表达式的结果。
2、输出的形式:
当按照程序要求选择了1或0之后,再输入表达式;如果选择的是1,则程序将自动运算出表达式结果;如果之前选择的是0,则程序将现将中缀表达式转化为后缀表达式并计算出结果。
3、程序所能达到的功能:
本程序能计算出含+、-、*、/、(、)等运算符的简单运算。
4、测试数据:
输入一个表达式,如果你之前选择的是“中缀表达式”,那么输入5*(4-2)#,那么输出结果是10;如果之前选择的是“后缀表达式”,那么输入5*(4-2)#,那么他将先转换成后缀表达式542-*#,再输出结果10。
如果输入表达式没有结束标示符#,如5*(4-2),那将不会输出任何结果,或出现错误结果。
(二)概要设计
为了实现上述操作,应以栈为存储结构。
1. 基本操作:
(1).intGetTop(SqStack*s)
初始条件:
栈存在;
操作结果:
若栈为空,则返回s的栈顶元素;否则返回ERROR。
(2).voidPush(SqStack*s,inte)
初始条件:
栈存在;
操作结果:
插入e为新的栈顶元素。
(3).intPop(SqStack*s)
初始条件:
栈存在;
操作结果:
若栈不空,则删除之,并返回其值;否则返回REEOR。
(4).voidInitStack(SqStack*s)
初始条件:
栈存在;
操作结果:
置栈为空。
(5).intEmpty(SqStack*s)
初始条件:
栈存在;
操作结果:
判定s是否为空栈。
(6).intOperate(inta,chartheta,intb)
初始条件:
操作数a和b存在,且theta是+、-、*、/四则运算;
操作结果:
返回a与b间theta运算的结果。
(7).intIn(chars,char*TestOp)
初始条件:
s为待判断字符,TestOp为已知的算符集合;
操作结果:
s为算符集合中的元素则返回1,否则返回0.
(8).intReturnOpOrd(charop,char*TestOp)
初始条件:
op为待确定运算符,TestOp为已知的算符集合;
操作结果:
确定运算符类型。
(9).charprecede(chara,charb)
初始条件:
a、b存在;
操作结果:
返回算符a和b的优先权高低。
(10).voidPrintOpnd(SqStack*s)
初始条件:
栈存在;
操作结果:
输出运算数栈。
(11).voidPrintOptr(SqStack*s)
初始条件:
栈存在;
操作结果:
输出运算符栈。
(12).voidStore(char*s,charch)
初始条件:
字符数组s存在,字符ch已知;
操作结果:
将ch存入数组s。
(13).voidChange(char*s1,char*s2)
初始条件;重罪表达式s1已知;
操作结果:
将中缀表达式s1转为后缀表达式s2。
2.本程序包含二个模块:
(1) 主程序模块;
(2) 中缀表达式求值模块以及中缀表达式转换为后缀表达式并求值模块
(3) 模块调用图:
主程序模块
中缀表达式求值模块
中缀表达式转换为后缀表达式并求值模块
(三)详细设计
1. 存储类型,元素类型,结点类型:
typedefstruct{//定义栈
intdata[SIZE];
inttop;
intbase;
}SqStack;
charOPSET[7]={'+','-','*','/','(',')','#'};
//定义OPSET字符数组为算符集合
charPrior[7][7]={
//算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=','',
'>','>','>','>','','>','>',
'<','<','<','<','<','','='
};
2. 每个模块的分析:
(1) 主程序模块:
intmain(){
chars=0,c;
while
(1){
printf("请输入‘1’或‘0’(1代表中缀表达式,0代表后缀表达式)\n");
c=getchar();
fflush(stdin);
if(c=='1'){//中缀表达式运算结果
printf("%d\n",EvaluateExpression_1());
}
else{//后缀表达式运算结果
printf("%d\n",EvaluateExpression_2());
}
do{
scanf("%c",&s);
if(s=='q'||s=='Q')
exit(0);
}
while(s!
='\n');
system("cls");
}
return0;
}
(2)intEvaluateExpression_1(){
//中缀求值
SqStackOPND,OPTR;
charch,theta,exp[100]={0};
inti=0,s=0,a=0,b=0,step=0;
InitStack(&OPND);
InitStack(&OPTR);
Push(&OPTR,'#');
gets(exp);
ch=exp[0];
while(ch!
='#'||GetTop(&OPTR)!
='#'){
if(!
In(ch,OPSET)){//不是运算符则进栈
if(In(exp[i+1],OPSET)){//未出现连续数字
Push(&OPND,ch-48);
ch=exp[++i];
}//if
else//出现连续数字
{
s=exp[i++]-48;
while(exp[i]>='0'&&exp[i]<='9'){
s=s*10+exp[i++]-48;
}
Push(&OPND,s);
s=0;
ch=exp[i];
}
}
else
switch(precede(GetTop(&OPTR),ch)){
case'<':
//栈顶元素优先权低
Push(&OPTR,ch);
ch=exp[++i];
break;
case'=':
//脱括号并接受下一字符
Pop(&OPTR);
ch=exp[++i];
break;
case'>':
//退栈并将运算结果入栈
theta=Pop(&OPTR);
b=Pop(&OPND);
a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
break;
}//switch
}//while
returnGetTop(&OPND);
}//EvaluateExpression_1
intEvaluateExpression_2(){//后缀求值
SqStackOPND;
charch,theta,receive[100]={0},exp[100]={0};
inti=0,s=0,a=0,b=0,step=0;
InitStack(&OPND);
printf("请输入一个中缀表达式:
\n");
gets(receive);//输入中缀表达式
Change(receive,exp);
printf("相应的后缀表达式为:
\n");
puts(exp);//输出对应的后缀表达式
ch=exp[0];
while(ch!
='#'){
if(!
In(ch,OPSET)){//不是运算符则压入栈中
if(exp[i+1]==''){//未出现连续数字
Push(&OPND,ch-48);
i+=2;
ch=exp[i];
}//if
else//出现连续数字
{
s=exp[i++]-48;
while(exp[i]>='0'&&exp[i]<='9'){
s=s*10+exp[i++]-48;
}//while
Push(&OPND,s);
s=0;
ch=exp[++i];
}//else
}//if
else{
theta=ch;
b=Pop(&OPND);
a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
i+=2;
ch=exp[i];
}
}
returnGetTop(&OPND);
}//EvaluateExpression_2(
3) 函数调用关系图
main()
EvaluateExpression_1()
EvaluateExpression_2()
3. 完整的程序:
#include"stdio.h"
#include"stdlib.h"
#defineSIZE80
#defineOK1
#defineERROR0
typedefstruct{//定义栈
intdata[SIZE];
inttop;
intbase;
}SqStack;
charOPSET[7]={'+','-','*','/','(',')','#'};
//定义OPSET字符数组为算符集合
charPrior[7][7]={
//算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=','',
'>','>','>','>','','>','>',
'<','<','<','<','<','','='
};
intGetTop(SqStack*s){
//若栈为空,则返回s的栈顶元素;否则返回ERROR
if(s->top==s->base)
returnERROR;
return(s->data[s->top-1]);
}
voidPush(SqStack*s,inte){
//插入e为新的栈顶元素
s->data[s->top]=e;
s->top++;
}
intPop(SqStack*s){
//若栈不空,则删除之,并返回其值;否则返回REEOR
inte;
if(s->base==s->top)
returnERROR;
else{
e=s->data[s->top-1];
s->top--;
}
returne;
}
voidInitStack(SqStack*s){
//置栈S为空
s->top=0;
s->base=0;
}
intEmpty(SqStack*s){
//判定s是否为空栈
if(s->base==s->top)
return1;
else
return0;
}
intOperate(inta,chartheta,intb){
//返回a与b间theta运算的结果
switch(theta){
case'+':
returna+b;break;
case'-':
returna-b;break;
case'*':
returna*b;break;
case'/':
returna/b;break;
default:
return0;
}
}
intIn(chars,char*TestOp){
//s为待判断字符,TestOp为已知的算符集合
intFind=0;
for(inti=0;i<7;i++){
if(s==TestOp[i])Find=1;
}
returnFind;
}
intReturnOpOrd(charop,char*TestOp){
//确定运算符类型,op为待确定运算符,TestOp为已知的算符集合
inti;
for(i=0;i<7;i++){
if(op==TestOp[i])returni;
}
return0;
}
charprecede(chara,charb){
//返回算符a和b的优先权高低
returnPrior[ReturnOpOrd(a,OPSET)][ReturnOpOrd(b,OPSET)];
}
voidPrintOpnd(SqStack*s){
//输出运算数栈
inti=s->base;
printf("StackOPND:
");
if(!
Empty(s)){
for(;i<(s->top);i++)
printf("%d",s->data[i]);
}
else
printf("");
printf("\n");
}
voidPrintOptr(SqStack*s){
//输出运算符栈
inti=s->base;
printf("StackOPTR:
");
for(;i<(s->top);i++)
printf("%c",s->data[i]);
printf("\n");
}
voidStore(char*s,charch){
//将ch存入数组s
char*p=s;
while(*p){
p++;
}
*p++=ch;
}
intEvaluateExpression_1(){
//中缀求值
SqStackOPND,OPTR;
charch,theta,exp[100]={0};
inti=0,s=0,a=0,b=0,step=0;
InitStack(&OPND);
InitStack(&OPTR);
Push(&OPTR,'#');
gets(exp);
ch=exp[0];
while(ch!
='#'||GetTop(&OPTR)!
='#'){
if(!
In(ch,OPSET)){//不是运算符则进栈
if(In(exp[i+1],OPSET)){//未出现连续数字
Push(&OPND,ch-48);
ch=exp[++i];
}//if
else//出现连续数字
{
s=exp[i++]-48;
while(exp[i]>='0'&&exp[i]<='9'){
s=s*10+exp[i++]-48;
}
Push(&OPND,s);
s=0;
ch=exp[i];
}
}
else
switch(precede(GetTop(&OPTR),ch)){
case'<':
//栈顶元素优先权低
Push(&OPTR,ch);
ch=exp[++i];
break;
case'=':
//脱括号并接受下一字符
Pop(&OPTR);
ch=exp[++i];
break;
case'>':
//退栈并将运算结果入栈
theta=Pop(&OPTR);
b=Pop(&OPND);
a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
break;
}//switch
}//while
returnGetTop(&OPND);
}//EvaluateExpression_1
voidChange(char*s1,char*s2){
//将中缀表达式转为后缀表达式
SqStackOPTR;
charch;
inti=0,sum=0;
InitStack(&OPTR);
Push(&OPTR,'#');
ch=s1[0];
while(ch!
='#'||GetTop(&OPTR)!
='#'){
if(!
In(ch,OPSET)){//不是运算符则进栈
if(In(s1[i+1],OPSET)){//未出现连续数字
Store(s2,ch);
Store(s2,'');//存入一个空格
ch=s1[++i];
}//if
else//出现连续数字
{
while(s1[i]>='0'&&s1[i]<='9'){
Store(s2,s1[i]);
i++;
}//while
Store(s2,'');//存入一个空格
ch=s1[i];
}//else
}//if
else
switch(precede(GetTop(&OPTR),ch)){
case'<':
//栈顶元素优先权低
Push(&OPTR,ch);
ch=s1[++i];
break;
case'=':
//脱括号并接受下一字符
Pop(&OPTR);
ch=s1[++i];
break;
case'>':
//退栈并将运算结果入栈
Store(s2,Pop(&OPTR));
Store(s2,'');//补入一个空格作为间隔
break;
}//switch
}//while
Store(s2,ch);
}//Change
intEvaluateExpression_2(){//后缀求值
SqStackOPND;
charch,theta,receive[100]={0},exp[100]={0};
inti=0,s=0,a=0,b=0,step=0;
InitStack(&OPND);
printf("请输入一个中缀表达式:
\n");
gets(receive);//输入中缀表达式
Change(receive,exp);
printf("相应的后缀表达式为:
\n");
puts(exp);//输出对应的后缀表达式
ch=exp[0];
while(ch!
='#'){
if(!
In(ch,OPSET)){//不是运算符则压入栈中
if(exp[i+1]==''){//未出现连续数字
Push(&OPND,ch-48);
i+=2;
ch=exp[i];
}//if
else//出现连续数字
{
s=exp[i++]-48;
while(exp[i]>='0'&&exp[i]<='9'){
s=s*10+exp[i++]-48;
}//while
Push(&OPND,s);
s=0;
ch=exp[++i];
}//else
}//if
else{
theta=ch;
b=Pop(&OPND);
a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
i+=2;
ch=exp[i];
}
}
returnGetTop(&OPND);
}//EvaluateExpression_2
intmain(){
chars=0,c;
while
(1){
printf("请输入‘1’或‘0’(1代表中缀表达式,0代表后缀表达式)\n");
c=getchar();
fflush(stdin);
if(c=='1'){//中缀表达式运算结果
printf("%d\n",EvaluateExpression_1());
}
else{//后缀表达式运算结果
printf("%d\n",EvaluateExpression_2());
}
do{
scanf("%c",&s);
if(s=='q'||s=='Q')
exit(0);
}
while(s!
='\n');
system("cls");
}
return0;
}(四)程序使用说明及测试结果
1. 程序使用说明
(1) 本程序的运行环境为VC6.0。
(2) 进入演示程序后即显示提示信息:
请输入‘1’或‘0’(1代表中缀表达式,0代表后缀表达式):
若输入1,则继续输入一中缀表达式,程序将计算出结果;
若输入0,则程序将继续提示:
请输入一个中缀表达式:
输入一中缀表达式
相应的后缀表达式为:
程序此后将显示转换后的后缀表达式,并输出结果。
2. 测试结果:
例如:
5*(6-4)#,输出结果为10.
3. 调试中的错误及解决办法。
(遇到时给出)
开始套用课本中算法模式,在调试过程中错误重重,经过单步调试后,出现了运行界面,但是未能输出正确结果;最后请班上其他同学指点,并改进算法,最终得出程序。
4.运行界面
先输入1,再输入表达式5*(6-4)#
先输入0,再输入表达式5*(6-4)#
(五)、实验总结(实验心得)
你在编程过程中花时多少?
零散的时间全部加上,大概有十多个小时。
多少时间在纸上设计?
没有在纸上设计。
多少时间上机输入和调试?
十来个小时。
多少时间在思考问题?
不知道,一两个吧。
遇到了哪些难题?
开始套用课本中算法模式,在调试过程中错误重重,经过单步调试后,出现了运行界面,但是未能输出正确结果;最后请班上其他同学指点,并改进算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构实验报告 表达式求值 数据结构 实验 报告 表达式 求值