简易计算器栈与队列试验报告

1、第三组专题二栈与队列实验报告简易计算器一.(1)问题描述通过模拟一个简单的计算器来进行+、-、*、/、人(乘方)等运算，从键盘上输入一算术表达式(一般为中缀表达式)，计算出表达式的值。(2)基本要求编写程序，要求可对一实数算术表达式进行简单的数学运算。可以识别带加减乘除等运算符及括号的中缀表达式。a.按照四则运算规则，求表达式的值。一般规则如下：1)先括号内，再括号外。2)先乘方，再乘除，后加减。b.同级运算从左到右顺序执行。c.如表达式有误，应给出相应的提示信息。(3)数据结构与算法分析解决表达式求值问题的方法之一是：第一步将中缀表达式转换为后缀表达式，第二步按后缀表达式求值。解题时可以结合

2、字符串的相关知识。(4)测试4.5+5+6.5*1.06=16.39二.(1)问题分析：计算机要计算一个式子，不能像我们一样计算，它需要把表达式由中缀表达式转换成后缀表达式，即逆波兰表达式。将一般中缀表达式转换为逆波兰表达式有如下转换过程：(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见，设该简单算术表达式的右端多加上了优先级最低的特殊符号“=”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。

3、做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。(5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。(2)问题实现及代码。1.菜单函数：使用switch函数根据输入的数字选择是否进入计算器valdCOUH<-实/父科学算M计翼立c.gut«chdi3ciSMTC("-.f.(md1fiCDLTt&

4、lt;<工的对Fe«dL11fhiB>,"«erid1i4ut*-w，«imd1i上口吐£你的旗徉皋f7intchoitejclnKholcejg1Ci*eflreturnjcaseli£tyttM；bkr匕叱曲JstiTingequations:trihixl-e(|go_cn-y4)*(-cauttjendlc<endl<<'',及尊我.以-i等号；cim>史qatLon.：E-idcu(rduatiariij.；3Mt“”揖缔If用吗？鼻诺*Ay有密惜加，二匚in>，g：

5、口一口ni-：-'.：广二!).:孙、士“广】广方;rienuf)2 .检测非法输入函数:int11legsl_char(ftr1ng£,int1)(一intj-S|0d)C1f6(1*=01£【4=5"j*iwtK*ri=,+,iitj",-,ii*j-,*ihj=7Tiisji='ii*n=¥(TiiMji=,)TiiMJi=T*7“或上原二桃三式I罟葆无其代苦式先字器期是拿法输入else<程序睥If",和F非沈的尹商人1IF"NMdLnrtiJTinigj)return1品.噎:；臂"二

6、-二吴J工工力者二:返I电)3 .双目运算符定义函数：完成对+,-,*,/,人的定义：-1ia«/1".*"Wpauraa=./；_c,:j一/dcubleD_Ope"ate(double,cha产。pdoubley)./qffN算符的运冬.z("double目；二-上耳工1通(叩)(case'+"1;a-x*yjbrcakjicase'-91:a=it-yjbrf*akjcase鼻'：a=1()/5break;case/*:a=x/ysbreakjcasex'：fl=pm«(>Jy);

7、bF«k59工堂包瘩来加&充方)励铀。血匚送拧运第四静定/菽虞巷卓return,aj4 .判断运算符的优先级，决定是压栈或者弹栈运用到计算中：charPrecEdeflchitropl>charop现(if(t(opl»»'+'|opl""-')&&(op2"'+"|op2=»«'''|cp2»=')'|op2»=*)11(<jpl=1*1|oDl="/，)4&

8、(op2=""+"|op2='-'op2=«'*Fopl'/*op2=»1)T|op2«=n)|(opl='A'8&Hop2»'+|op2=»''|op2="*'op2='/'op2=P)R0p2=»T»1)return，$"上述情况下栈项运算符优先蜜高于特定运靠符凄弹栈if(opl='('&aop2=,j,)|(Qpl=,=,Sfiop2=1=1)

9、return;elsereturn"$5 .括号匹配检测函数:Jln-t量=叼>七op=曰学<hor"utmuMl&cjj,ah*“£W工1-1&卜)4ifCsi»%£*>c9h't-IB£k|_忙OpJ-aLAJ1izaps4-1MF4CIe_TOpXJ=I1申UILJ3f匚口ai:事工,痛耳.><育;MYku“dJLr*oX-i*#*1*。j，/ET,=1.二一.一产产pop-0Jl一v>A+。牡q户*-eJCUQU"tY<"JS-Sft-A-&

10、quot;*eLrH1产片信近1JI-EUB-J(K'P/''.-_<'etur'm【主：一,6 .运算栈：分为运算符栈和运算数栈:口IIHUHatAEli二(public:doublenuriaOiMt(CfJ.“35-arzt)rf-、1肃厮箭密1-g：I*wjii+)xCM，top«Qj.vddptiiHdwr笔一二匚->E二，一，'(nurtop=nstop10*(a>-”.j丁二三一：七一尸二二二-二于关)期曲&port)top，double力>uniMi".个uE+dFJgnot邺卜

11、电drtfflHHmfarri上。与暝工苛注公s：专李：印三4"wthublefteLld|.：).-：-'3:i*liN*nE年1>Mfidlift；.7'-lop*；In*，art4-tTArLfpublic;<JirCptfr|LffiMJInttopvoidStart(/楞始化函裁桎疮空校京成1'="：:定三大:hW>X.P"J'="p.ftnr(1riti-»1idCLEM;i+1)aiperIJ-IIlKljtap-:一彳.r上一wH1pu*(fgv*>d口«=top

12、jajtop*5与救事权不同一或段薪药窜谶升.>char心户£)(top-7charop-cpe|top|tep.fL七呼nl'Llbirrturnepi-；-='=一Jrh«r-gerT>0p()creturn口产之中-二h/15r法/7.算式计算函数（最关键函数）：用于对用户输入的算式进行计算，给出最后结果:void工QingWuatlon1“池,(-lUHTackndb»r.二.一二厂三金QPERitscknjnber.rta"tj)pcjer.start；)i-:-IntiMtjEtarpTUfi；doublejnja

13、il./uau：wiiiletequationiJJ-rW)(Lef>*+j、吓广宜芝式金兑5ji(CTjnic"ilcnl.-1*")(5iK，L潮人有说】比有验入强止荷耳一等号-=-"<c?idljrMuMr._3E:二三,E''jjutlei1r=il1rgfllchar(eqi_»ticwi|Icn-1以Hne=w)"rtiurir；.-t-rJle-HTCKeuAticfi)：if<ic-ejrrturp,/百号区丁台:-：->?：亍三二1.三三E(i+tequationlJi-'Uta

14、squtTionLi'f-':')(*1k*iwr.冲帆坤*MmjZIf；(equarioij*l<'9,eqi*atiznfj4-J.>?'iieqL3tjpni+JI-'.'nuiber.1讦t)"；器-出-=£F式量=二-r；工-二广一二.-.W-总seHEatlW"".-iflt21=ljJhlk|equallcnUr口b-11Luiki)t-a*|(,.nud|rurriKr.top-r-"日上七1>“-j%11Hl一?K-Jiuee-1.tlwlieqwTla

15、Clil'CI(;凶，如卡丁国uatlcMHI；“：-r-必-:y二-(幽)tf、+!)!：.?，”，-.op"1讣i>jelit-:=-二-二cBa*Fp二一甲¥"tTor：rEdJ，.utfr：?位对小团匕叫小p-Pr«cdf;tr>p1|tirTp2;；if(p-u/'l-二一if'p-'>'I|p-»)<ilK”PW严"，:二-_fjft''学好M力lrw再干炉量"二：步hllxIrep口-'51tra1-11卬-MR，：Isi.

16、：EpEr.pcpi)juil-rui4K<-pof'O!MTt朋即,二；/iF%.孙同山.，丁二二二二二二二（rHfrH,同irrtinj）11岫-中应叫h|山-Y|曲-多（1nPTk-,iur-：iiiEr-丁中卜】£.：冲一，卜厂"I-消*0日】；ibTTplttr*丁卬；邙心tEL：E3-/-）ii-vi：r；-''：.-t-；-T-r-k师小rlsr杯：网，印五吨匕Ih.tutewft-ctE(rti«>rvi)；c»t<*qwHiMrmtem.舶尬rlw:匚由中圜吟博缶一依LTjrM出1匚那/eJR&

17、#187;*-r:J苗希#.复就.=芈号j拄茅：-«*-fl4-KT3«0DG«避百使中卫Y第请通、.y吉.SflAn：一括号检测:请输入算式,以(等号)结束.2+1+(2+3=翳醯戢是请输入y否则输入叱非法输入检测:请输入算式，以(等号)结束.1+1$=嚣酷既编野鬻烷四.MFC界面介绍.我们不满足于DC限制的黑框框界面，所以我们运用了MFC界面。(1)界面初步简介：(2)对程序的改动:原C程序的拆分栈的定义定义两个样散于栈SB?5tt规定一strings注存数字与运亘计蛔病也绑定CSTRIMG短用于显示，二"函接下因为翊用I巨国故.也就代为了计算丈03

18、徭止CMrWE：栈的定义与，fIV.UWC.Re”(PuU<:out4enunilCOO;HltopvoidtfartO.VOBW(C2”ooufUpcrtr©cable9sCFopO:wwinoll:数字栈运算符栈计算函数潮月计算函数，并道个double生的钻果用lesull接收返叵约果判斯，仙果result与其整数部分的直相同则学过double法挨为int再译按为享符数组如果不等则double转:馔为字符物据斗以后肿傩为。的字符上处苴X，控位数输土,使得给果显示更人性化：新年部分）mShow增加新的字符效组，完成结果显示计算式输入函数«c千八0.'g)；5

19、aK*MdBu28o/TOOOiCMBAMMi11J抬Wirtcwl：f/«,*|l«CMOnBo<lkM6<.nor?0(toooAC-itiomNyf55wb«MD-attire-1>$<«-'：Upd»r«OMM«ALMl技植1（BUTTON1）举例，CSIRING类型，mshow拮加字符T对数据进,亍更新SIRING类型，oquation妈加字符Tqwttoe-guxonwlbisQQU*»oenorM)IXVteOMKAlWk退珞缝（一健）羊冽.m_Show,hequati

20、on都去掉最亭位对数坦送行更新完全消除键（AC镀）举例:洁士mStx）w，Lequation方数据遇冲史歼(3) 对C+程序的改进:改进的报错系统即时椎查画崇培收到易阖话叫按邮按下的信息!九数.使用用户染蚌及时发现输人命.避叠了出错率新洽入的演愉曜完视计算五就人错误时，茄诙用算也5对话恒.据不用谙!并更我出达为非不触反底翩磁亘十MFC工钿住先天肪错-我11对于用户的弹人汽式他te理的限制.即只差通过按卜按钮输入信息,所以用户不解卿”、不常美办左括号的倒搭,初步纠错据讨的捌羁讲一步叫债此时式锚入#完全,只能对括号此时川子第A完全，谶"括号肛配送进行纠舶.行钿步纠惜。ri.，即如黑之箭为

21、空.则总接输人:如果之前不是*，"t,必定出错则弹出指借对话相asrtMl1T：>>"fPirgtJlgBhl：llci9Am«i*l,BP1-"tfi上4；冉iconH.-uC.H-'a-.nimrtfc-.i*,咽.ifimhutiEiMrtfcm*；L_p_Iea#?mUpHMttiFAi汨-心MMI，iHwH(vqudrilcwi>qtjMbriivngZ1-11«da，l|«tuAH)|K|u«k.injHih3-1J共|M|uJlkiH4QHfb9HJfHiItT|""

22、;T|rqflg/与FE1f门qitan>n*加、减、乘、除、退格键的报错提示程序的展示计算式子：8.5+9f(3+4.5*6)-(7.658,9)*12)=23.8/wx清除展示报错展示五.优势与不足：优势：(1)做出了界面，不再是黑框框(2)报错系统完善，基本不会出错。(3)结果显示正确，不会出现多余的0。不足：(1)虽然做出了界面，但是还不是很优美。(2)功能还不是很强大，不能进行三角函数的运算及其他运算。这些缺点我们都会再以后的学习中克服掉！源代码：#include<iostream>#include<cmath>#include<string>

23、;#include<iomanip>usingnamespacestd;voidmenu();/位于calculate函数后面的菜单函数声明doubleD_Operate(doublex,charop,doubley)/双目运算符的运算定义(doublea;/计算结果switch(op)(case'+':a=x+y;break;case'-':a=x-y;break;case'*':a=x*y;break;case'/':a=x/y;break;case'"a=pow(x,y);break;/哥运算包

24、括乘方和开方)/因为都是利用double进行运算因此不定义取模运算returna;)charPrecede(charop1,charop2)判断符号的优先级op1在返回的结果符的左边op2在右边/用于判定运算符的优先级以决定是把运算符压栈还是把栈内的运算符弹出来进行计算(if(op1='+'|op1='-')&&(op2='+'|op2='-'|op2=')'110P2='=')|(op1='*'110P1='/')&&(op2=

25、9;+'|op2='-'|op2='*'110P2='/'110P2=')'110P2='=')|(op1=w&&(op2='+'|op2='-'|op2='*'110P2='/'110P2=')'110P2='=')return'>'/上述情况下栈顶运算符优先级高于待定运算符需弹栈if(op1='('&&op2=')')|(o

26、p1='='&&op2='=')return'='elsereturn'<')intillegal_char(strings,inti)/非法输入字符判定函数(intj=0;while(j<i)(if(sj>='0'&&sj<='9')j+;elseif(sj='+'|sj='-'|sj='*'|sj='/'|sj='.'|sj='('|sj=

27、9;)'|sj='A')j+;/以上都是标准的数字字符和运算符如若存在其他形式的字符则是非法输入else(cout<<"程序终止，存在非法的字符输入！!"<<endl;return0;)return1;/没有非法字符返回1否则返回0)intmatch(strings)/栈结构的括号匹配检测函数(inti=0,top=0;charstack50;while(si!='0')(if(si='(')stacktop=si;top+;)/push左括号压入栈内if(si=')')if(s

28、tacktop-1='(')(inta=i+1;stacktop-1=NULL;top-;/把与右括号匹配的左括号弹掉else(cout<<"括号输入有误"<<endl;return0;/多了右括号括号失陪返回非法/pop'('i+;if(top!=0)(cout<<"括号输入有误"<<endl;return0;/多了左括号括号失陪返回非法return1;/返回合法classNUMstack/运算数栈(public:doublenum1000;inttop;voidstart

29、()/初始化栈清空栈顶指针置底(for(inti=0;i<1000;i+)numi=0;top=0;voidpush(chara)/因为有多位数的运算因此不能一压栈就提升栈顶指针(numtop=numtop*10+(a-'0');/把字符转成数因为每次入栈之前要乘10所以初始化要清0doublepop()(top-;doublenumber=numtop;numtop=0;returnnumber;)/弹栈函数弹掉栈顶元素栈顶归0top指针下降doublegetTop()/取栈顶元素但不必弹栈returnnumtop-1;voidlift()/提升top指针的函数top+

30、;classOPERstack/运算符栈public:charoper1000;inttop;voidstart()/初始化函数栈清空栈底放一"="用于判定算式结束oper0='='for(inti=1;i<1000;i+)operi=NULL;top=1;/栈顶指针置于栈底的上一位voidpush(chara)opertop=a;top+;/与数字栈不同一压栈就可以提升指针charpop()top-;charop=opertop;opertop=NULL;returnop;/弹出计算符用于计算chargetTop()returnopertop-1;/

31、取栈顶符号但不弹栈可用于判定优先级;voidcalculate(stringequation)/算式计算函数(关键函数)NUMstacknumber;/定义运算数栈变量numberOPERstackoper;/定义运算符栈变量opernumber.start();oper.start();/把两个栈初始化inti=0,len=0,k;charp,sig;doubleyuan1,yuan2;while(equationi!='0')len+;i+;/计算等式长度lenif(equationlen-1!='=')cout<<"输入有误！没有输入

32、终止符号等号“=""<<endl;return;/检测有没有结束符等号"="intle;le=illegal_char(equation,len-1);if(le=0)return;/有非法字符不进行后续计算le=match(equation);if(le=0)return;/括号匹配非法不进行后续计算for(i=0;i<len;i+)初步确定合法后开始计算算式if(equationi>='0'&&equationi<='9')number.push(equationi);/压

33、数字字符入栈if(equationi+1<'0'|equationi+1>'9')&&equationi+1!='.')number.lift();/当整个多位运算数读取完毕后，运算数栈栈顶指针才能提升elseif(equationi='.')/小数压栈代码intx=1;while(equationi+x>='0'&&equationi+x<='9')number.numnumber.top+=(equationi+x-'0')

34、/pow(10,x);/第x位小数入栈x+;x-;number.lift();i=i+x;elseif(equationi='(')oper.push(equationi);/左括号无条件压栈)else/数乘方左括号判断完毕后其他运算符的分类讨论(if(oper.top=1)/运算符栈为空运算符可以无条件入栈oper.push(equationi);else/运算符栈不为空则要进行优先级判断(chartemp1=oper.getTop();/取出栈顶符号chartemp2;/待入栈符号temp2=equationi;p=Precede(temp1,temp2);if(p=

35、9;<')oper.push(temp2);/栈顶符优先级较低现在待定的运算符就可以入栈了if(p='>'|p='=')(charrep=p;/当栈顶符优先级不低于待入栈的符号则运算符栈不停地弹栈/进行运算直到低于待入栈符号为止rep用于记录比较结果要多次进行判断while(rep='>'|p='=')&&(oper.top-1>0)(sig=oper.pop();yuan1=number.pop();yuan2=number.getTop();/靠前的一个运算数只要取得不要弹出来if(sig='/'&&yuan1=0)/yuan1是双目运算符后面的第二运算元(cout<<