长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx
- 文档编号:15567972
- 上传时间:2023-07-05
- 格式:DOCX
- 页数:11
- 大小:29.19KB
长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx
《长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx》由会员分享,可在线阅读,更多相关《长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx(11页珍藏版)》请在冰点文库上搜索。
长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告
批阅
实验报告
年级—班号—学号—
实验名称:
栈的实现及其应用:
算术表达式的计算
实验日期2016年12月2日
实验报告撰写容
一、实验环境
四、数据结构与算法思想描述
二、实验目的
五、程序清单
三、实验容
六、程序执行结果及其分析
计算机科学与技术系
2016年制
实验环境
32位操作系统下的Window平台MicrosoftVisualC++
实验目的
掌握栈的实现及使用
三、实验容
1.实现栈的存储结构
2.实现栈的基本操作的有关算法
3.利用栈解决*算术表达式求值问题
四、数据结构与算法思想描述
顺序读取中缀表达式:
1、当遇到数字时,将数字入数字栈
2、当遇到操作符时,与操作符栈栈顶比较:
If(当前操作符优先级大于操作符栈栈顶的优先级)
If(非”)”操作符)将当前操作符进操作符栈;
Else
Wh订e(操作符栈栈顶不等于”(“)
取操作符栈栈顶及数字栈的两个数进行运算,并将结果压入数字栈;Else
If(非(“操作符)
Wh订e(操作符栈栈顶不等于"(“)
取操作符栈栈顶及数字栈的两个数进行运算,并将结果压入数字栈;Continued直到当前操作符比栈顶操作符优先级大)
Else将当前操作符进操作符栈;
3、While(操作符栈非空)
操作符栈栈顶及数字栈的两个数进行运算,并将结果压入数字栈;
4、在数字栈取最后结果并输出。
五、程序清单
//10*8"2+16・3+5*(5・2*5+3・01)/4-(-10)+0.1000060+4.00416-40=666.666666
//100+(-100)-(-10'2)=100
//(((2016-2017+(((2015-2014))))))=0
//-l+(((((((((r0))))))))+100%W2=0
#inc1ude
#include
#include
#include
#inc1ude
#include
usingnamespacestd;
constintMAX=105;
typedefdoubleType;
typedefstruct
TypeTypeStacklMAX]:
charcharStackiMAX]:
intTypeTop,charTop;
(Stack;
//初始化栈
voidInitStack(Stack*S)
{
S->charTop=S->TypeTop=0;
}
//判断charStack是否为空
boolIsEmpty_Char(StackS)
{
returnS.charTop==0;
}
//判断TypeStack是否为空
boolIsEmptyType(StackS)
{
returnS・TypeTop==0;
}
//判断charStack是否为满
boolIsFull_Char(StackS)
returnS・charTop==MAX;
//判断TypeStack是否为满
boolIsFull_Type(StackS)
{
returnS・TypeTop==MAX;
}
voidPushChar(Stack*S,charch)
{
//charStack不为满则入栈,否则输出提示
if(!
IsFull_Char(*S))
S~>charStack[S->charTop++]=ch;
else
cout<<"TheCharStackIsFull!
< } voidPushType(Stack*S,Typea) { //TypeStack不为满则入栈,否则输出提示 if(! IsFull_Type(*S)) S->TypeStack[S->TypeTop++]=a; else cout<<"TheTypeStackIsFull! < charPopChar(Stack*S) if(! IsEmptyChar(*S)) { S->charTop-一; returnS->charStack[S->charTop]; } else cout< "< returnT; } TypePopType(Stack*S) { if(! IsEmptyType(*S)) { S->TypeTop--; returnS->TypeStack[S->TypeTop]; } else cout<<"TheTypeStackIsEmpty! "< returnT; } charTopChar(StackS) if(! IsEmptyChar(S)) returnS.charStack[一一S.charTop]; else cout<<"TheCharStackIsEmpty! "< } TypeTopType(StackS) { if(! IsEmptyType(S)) returnS.TypeStack[一一S.TypeTop]; else cout<<"TheTypeStackIsEmpty! "< } TypeCalculate(Typeleft,Typeright,charop){ Typevalue=0; switch(op) case 屮: value= left+right; break; case •i ••■ • value= left-right; break; case ***: value= left*right; break; case 7': if(right ! =0) value=left/right; else cout«被除数不能为零! "«endl;break; case: if(right! =0) value=(int)left%(int)right;else cout«"被余数不能为零! "«endl;break; case1**: value=pow(left,right): /♦value=1; if(right>=0) while(right--) value*=left; else { right=-right; while(right--) value/=left; returnvalue; voidComputer(char*midequotion,Typelen) Typeright,left,result; char*pmidequotion=midequotion; charafter_equotion二''; map Oper['tt']=1; Oper['(']=2; Oper['+']=3; Oper[']=3; Oper[r*r]=4; Oper['/'] =4; Oper['%']=4; Oper[r]=5; OperI')'] =6; StackMyStack; InitStack(&MyStack); Push_Char(&MyStack,*#*);chartopoper,current_oper; for(;*pmidequotion! 二*\0*;) { topoper=TopChar(MyStack): currentoper=*pmidequotion;if(! Oper[currentoper]) { PushType(&MyStack,strtod(pmidequotion,&pmidequotion)); continue; }//endif else//为操作符 if(Oper[currentoper]>Oper[topoper]) if(current_oper! =')') Push_Char(&MyStack,currentoper); else { while(topoper! ='(') { right=PopType(&MyStack): if(! IsEmpty,Type(MyStack)) left=Pop_Type(&MyStack): else right, left=0; PushType(&MyStackfCalculate(left,TopChar(MyStack))); PopChar(SMyStack); topoper=TopChar(MyStack); } PopChar(&MyStack); }//endelse }//endif else { if(current_oper=='(') Push_Char(&MyStack,currentoper); if(*(p_midequotion+1)==‘-‘) PushType(&MyStack,0); } else { right=PopType(&MyStack): if(! IsEmptyType(MyStack)) left=PopType(&MyStack): else left=0; PushType(&MyStack,Calculate(left,right,topoper)); Pop_Char(&MyStack); continue; } }//endelse }//endelse pmidequotion++; }//endfor topoper=PopChar(&MyStack); while(topoper! = { right=Pop_Type(&MyStack): if(! IsEmptyType(MyStack)) left=PopType(&MyStack): else left=0; PushType(&MyStack,Calculate(left,right,topoper)); topoper=PopChar(&HyStack); } //cout< PopType(&MyStack))«endl; printf(PTheResult=%lf\n\nM,(result=Pop_Type(AMyStack))); } intmain() { chars[MAX]="”; Typei=0; cout«"请输入你要求值的表达式! (以-1结束)\n"; while(cin»s&&strcmp(s,h-lh)! =0) { Computer(s,strlen(s)); cout«"请输入你要求值的表达式! (以-1结束)\n"; } return0; } 六、程序执行结果及其分析 对“+”,,“/”,“%”,运算的实现 可运算多位数和小数,求余,求平方,括号里包含负数如(-1),及首个数字为负数如 -1+1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 长沙 理工大学 数据结构 实现 应用 算术 表达式 求值 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)