C++與數(shù)據(jù)結(jié)構(gòu)專(zhuān)題設(shè)計(jì)三簡(jiǎn)易計(jì)算器

1、C+當(dāng)數(shù)據(jù)結(jié)構(gòu)專(zhuān)題設(shè)計(jì) 簡(jiǎn)易計(jì)算器 目錄 一 .問(wèn)題描述2 二 .具體要求2 三 .數(shù)據(jù)結(jié)構(gòu)3 四 .設(shè)計(jì)與實(shí)現(xiàn)3 1 .系統(tǒng)首頁(yè)：4 2 .進(jìn)行簡(jiǎn)單的四則運(yùn)算5 五 .測(cè)試與結(jié)論11 1 .表達(dá)式錯(cuò)誤的情況12 2 .所要計(jì)算的數(shù)據(jù)過(guò)大或過(guò)小的情況15 六 .總結(jié)與思考17 七 .附源代碼17 一.問(wèn)題描述 由鍵盤(pán)輸入一算術(shù)表達(dá)式，以中綴形式輸入，試編寫(xiě)程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換成一棵二叉表達(dá)式樹(shù)，通過(guò)對(duì)該的后序遍歷求出計(jì)算表達(dá)式的值。 二.具體要求 a.要求對(duì)輸入的表達(dá)式能判斷出是否合法。不合法要有錯(cuò)誤提示信息。 b.將中綴表達(dá)式轉(zhuǎn)換成二叉表達(dá)式樹(shù)。 c.后序遍歷求出表達(dá)式的值 三.數(shù)據(jù)結(jié)構(gòu) 一

2、棵表達(dá)式樹(shù)，它的樹(shù)葉是操作數(shù)，如常量或變量名字，而其他的結(jié)點(diǎn)為操作符。 a.建立表達(dá)式樹(shù)。 二叉樹(shù)的存儲(chǔ)采用了鏈?zhǔn)酱鎯?chǔ)。 當(dāng)要?jiǎng)?chuàng)建二叉樹(shù)時(shí)，先從表達(dá)式尾部向前搜索， 找到第一個(gè)優(yōu)先級(jí)最低的運(yùn)算符， 建立以這個(gè)運(yùn)算符為數(shù)據(jù)元素的根結(jié)點(diǎn)。 注意到表達(dá)式中此運(yùn)算符的左邊部分對(duì)應(yīng)的二叉綺為根結(jié)點(diǎn)的左子樹(shù)，右邊部分對(duì)應(yīng)的是二叉綺為根結(jié)點(diǎn)的右子樹(shù)，根據(jù)地這一點(diǎn)，可用遞歸調(diào)用自己來(lái)完成對(duì)左右子樹(shù)的構(gòu)造。 b.求表達(dá)式的值。求值時(shí)同樣可以采用遞歸的思想，對(duì)表達(dá)式進(jìn)行后序遍歷。 先遞歸調(diào)用自己計(jì)算左子樹(shù)所代表的表達(dá)式的值， 再遞歸調(diào)用自己計(jì)算右子樹(shù)代表的表達(dá)式的值， 最后讀取根結(jié)點(diǎn)中的運(yùn)算符， 以剛才得到的左右

3、子樹(shù)的結(jié)果作為操作數(shù)加以計(jì)算，得到最終結(jié)果。 四.設(shè)計(jì)與實(shí)現(xiàn) 為了使用二叉樹(shù)實(shí)現(xiàn)表達(dá)式的順序運(yùn)算，我們分別構(gòu)造了結(jié)點(diǎn)類(lèi),用來(lái)作為二叉樹(shù)的基本結(jié)構(gòu)，后構(gòu)造二叉樹(shù)類(lèi)，構(gòu)造函數(shù)并建立根節(jié)點(diǎn)，先對(duì)二叉樹(shù)的根節(jié)點(diǎn)進(jìn)行運(yùn)算，再通過(guò)對(duì)當(dāng)前節(jié)點(diǎn)的左孩子右孩子節(jié)點(diǎn)進(jìn)行判斷、計(jì)算、刪除，以一個(gè)遞歸調(diào)用函數(shù)即后序遍歷，從根節(jié)點(diǎn)開(kāi)始計(jì)算，如果子樹(shù)中不為空且不為數(shù)據(jù)則先遍歷左子樹(shù)然后遍歷右子樹(shù)然后計(jì)算根節(jié)點(diǎn)，從而實(shí)現(xiàn)按照運(yùn)算符優(yōu)先級(jí)順序完成表達(dá)式計(jì)算的功能。并在每次計(jì)算完成后詢(xún)問(wèn)操作者意愿從而決定是否進(jìn)行下一次運(yùn)算。 以下介紹程序功能的實(shí)現(xiàn)： 1 .系統(tǒng)首頁(yè): 功能提示，輸入待計(jì)算的表達(dá)式，以完成計(jì)算: 相應(yīng)代碼: s

4、ystem(cls); * 二叉樹(shù)計(jì)算器endl; *charc; while(choice=y|choice=Y)(cout * endl; cout cout * endl; coutinfix; cout n;cout”表達(dá)式為：infixn; 2 .進(jìn)行簡(jiǎn)單的四則運(yùn)算 對(duì)輸入的表達(dá)式首先判斷正誤，然后按照運(yùn)算的優(yōu)先級(jí)分別進(jìn)行運(yùn) 行，并且分別輸出每步運(yùn)算的結(jié)果。先進(jìn)行乘方，然后乘除，最后再 計(jì)算加減，先算括號(hào)內(nèi)后算括號(hào)外，正確度一目了然。 1P1P：5 5 學(xué)習(xí) K+K+粕未 二叉樹(shù)計(jì)算器 MHJCJOCXHMXMM：MJOTM：MEMKKJflffMM：NKMJCXMXJCKMlCJf

5、fMM：JCXJtMlCMlgMJtMlCXMJtMJCJClfIffXME，JtMiMiffMJtMIt 請(qǐng)輸入表達(dá)式； 13+2513+25- -36*2/9)263/9)2 是否要重新運(yùn)行?輸入小八: irr式的是 達(dá)間果 表中72結(jié) 76 是否要重新運(yùn)彳 C 榆入CN二Y 請(qǐng)輸入表達(dá)式： - -1212*56”*56”- -24/624/6 是否要重新運(yùn)行?輸入： inin (1)對(duì)于負(fù)數(shù)也可以進(jìn)行相應(yīng)的加減乘除以及乘方的運(yùn)算。對(duì) 于負(fù)數(shù)的運(yùn)算，也和正數(shù)一樣，先算括號(hào)內(nèi)的后算括號(hào)外的，其 次算乘方，再算乘除，最后進(jìn)行加減的運(yùn)算 S3S3口將習(xí)”+小專(zhuān)道闔出砂法諭名工冉/是否要重新運(yùn)行?

6、輸入：y y 請(qǐng)輸入表達(dá)式； - -12+(15/912+(15/933- -2 2 震達(dá)式為?- -12*12*A Aa a 中間的算結(jié)果：- -12125270477252704772 結(jié)果是二寸 是否要重新運(yùn)行?輸入(Y/N(Y/N： 負(fù)數(shù)的加減乘除:E3E3- -D D：XgXg c+c+1,1,exe,exe, cztczt 叵痙 果40結(jié) 二算 -流是達(dá)間2果表中T結(jié) E3E3。；學(xué)習(xí)專(zhuān)期即臥未命名 LoeLoe 請(qǐng)輸入表達(dá)式; 需藉結(jié)晶 - -12*12*+L1- -2 2 結(jié)果是 128128 是否要重新運(yùn)行?輸入丫川： 負(fù)數(shù)的乘方運(yùn)算: (1) 正指數(shù)哥運(yùn)算: d dDADA

7、 學(xué)習(xí)+宙期設(shè)計(jì)惘未命名LEX- 回 S3S3 是否要重新運(yùn)行?輸入 4/4/心;y y 請(qǐng)輸入表達(dá)式： 5A A2 2 .算25:式的是達(dá)間果慮中T結(jié) 是否要重新運(yùn)行?輸入 (2)負(fù)指數(shù)哥運(yùn)算: 可以進(jìn)行小數(shù)的計(jì)算，對(duì)于小數(shù)采用浮點(diǎn)數(shù)的存儲(chǔ)方式和輸出 方式，計(jì)算精度可以取到小數(shù)點(diǎn)后五位。 小數(shù)的加減乘除: 小數(shù)的運(yùn)算，依然按照先乘除后加減，先算括號(hào)內(nèi)后算括號(hào)外的順序運(yùn)算D：1，學(xué)習(xí) F+守或凌計(jì)、恢夫拿名l.exe是否要重新運(yùn)行苫輸丫川 X 少 請(qǐng)輸入表達(dá)式士 1 1.J25*1.45.J25*_502.4.074.07 中間的計(jì)算結(jié)具,2.G54474.104472.G54474.1044

8、7- -0.765530.76553 結(jié)果是 t t- -1.014331.01433 是否要重新運(yùn)行?輸入 小數(shù)的乘方和開(kāi)方： (1)正小數(shù)哥次方： r 口D學(xué)習(xí) q 爐專(zhuān)題設(shè)計(jì)甲 n n 豐含11 皿 Q Q 件否要重新貶吁?輸入 d d 而好請(qǐng)輸入袤達(dá)式 I I 1.2343.44 l.J2b.b3Z2.4bl.J2b.b3Z2.4b- -4.H74.H7 中間的計(jì)算結(jié)果; 1.2343,41.2343,4 2.051222.05122 若果是:2 2- -6613366133 是否要重新運(yùn)吁?輸入(Y(Y，NXNX (4)開(kāi)負(fù)小數(shù)次方:E,OiVE,OiV 學(xué)2G+有班*- -EAEA

9、 未翁生 l.exfl.exf 是否要重新運(yùn)仃？輸 A4A4 NmNm 丫請(qǐng)輸入表達(dá)式; L234L234 氣- -2.3?32.3?3 需1詁間.3果表由T結(jié) ：1,2341,234A A( (- -2*3312*331 算結(jié)梟 0.6126830.612683 是否要重新運(yùn)行?輸入“八 1”1” (3)開(kāi)正小數(shù)次方: 是否要重新運(yùn)彳產(chǎn)輸入 4 4 小 X1 1 請(qǐng)輸入表達(dá)式; U.lbB.SU.lbB.S 是否要重新運(yùn)行孑軸八Y/NY/N： 杲 4 果鉆 -算式的 達(dá)間4果表中電結(jié) r S3笛：字事工+博蹬tt剛未能ELEKE 是否要重新運(yùn)行?輸入V 清榆人走達(dá)式二 0.160.16A A

10、 0.5 是否要重新運(yùn)行?輸入： IH 五.測(cè)試與結(jié)論 此報(bào)告在C-Free5.0環(huán)境下進(jìn)行測(cè)試。C-Free是一款C/C+噪成開(kāi)發(fā)環(huán)境（IDE）。C-Free中集成了C/C+弋碼解析器，能夠?qū)崟r(shí)解析代碼，并且在編寫(xiě)的過(guò)程中給出智能的提示。C-Free提供了對(duì) 目前業(yè)界主流C/C+瑞譯器的支才I,可以在C-Free中輕松切換編譯器?？啥ㄖ频目旖萱I、外部工具以及外部幫助文檔，使在編寫(xiě)代碼時(shí)得心應(yīng)手。完善的工程/工程組管理使你能夠方便的管理自己的代碼。 以下是各種測(cè)試用例。注：較為簡(jiǎn)單和常規(guī)的測(cè)試用例在上一部分”算法的實(shí)現(xiàn)”中已經(jīng)給出，下面只給出一些具有代表性的測(cè)試用例。 1.表達(dá)式錯(cuò)誤的情況 -

11、*5臬2.結(jié)E:1昇2 :式的是達(dá)間,5果-0結(jié) 在表達(dá)式錯(cuò)誤的情況下，程序能夠運(yùn)行，但是不能夠正常運(yùn) 算，而是給出錯(cuò)誤的提示信息，提醒重新輸入正確的表達(dá)式。 下圖表示以0作為除數(shù)時(shí)程序所給的提示信息“Infinity” ”射表達(dá)式：g g 1 1 表達(dá)式為 t t-i/e 中間的 M M 算結(jié)果： 1nfLnlty0 結(jié)果是； 足否要重薪運(yùn)行7輸工 n 下圖為計(jì)算表達(dá)式0八（-3）時(shí)候的輸出，由于表達(dá)式?jīng)]有數(shù)學(xué)意義，所以也就沒(méi)有正確的結(jié)果，因而程序運(yùn)行后得到的結(jié)果是aInfinity: 下圖顯示的是輸入的表達(dá)式不符合數(shù)學(xué)規(guī)律時(shí)的錯(cuò)誤提示 信息。 Z:Use01Administr&tc

12、r.Dmsmop又.忸:計(jì)苴號(hào),exe 請(qǐng)輸入表達(dá)式二 表達(dá)式無(wú): 中間的計(jì)算結(jié)里， - -1515HaHHaH 結(jié)果是:WNWN 是否要重新運(yùn)行?輸入： 下圖表示輸入表達(dá)式中含有不合法的字符， 例如字母時(shí)候,程序運(yùn)行時(shí)所給的提示信息。2121CtCt UsersUsers AdministratorAdministrator DetktopDetktopLL視計(jì)算矚 ewew 豆否要重新運(yùn)廳才輸入*”J J 清輸入表這式： a.+La.+L 麥達(dá)式為 Bt*XA*!WM*MWM*M- -*W*W- -MM/: 是否要重新運(yùn)行?諭入 CNCN 卜二 9 9 請(qǐng)輸入表達(dá)式， m979n?$9?9

13、?m979n?$9?9?.99999*3 中間的計(jì)算結(jié)果；InfinitInfinitv v 結(jié)果是(frfinity(frfinity 是否要重新運(yùn)行?輸入YN= = 六.總結(jié)與思考 七.附源代碼 #include #include #include #include #include利用stack頭文件來(lái)構(gòu)造兩個(gè)棧用來(lái)存儲(chǔ)數(shù) 據(jù)和運(yùn)算符 usingnamespacestd; boolIsOperator(stringmystring)判斷參數(shù)string是否是 運(yùn)算符是返回邏輯值true ( if(mystring=-|mystring=+|mystring=/|mystring= =*|

14、mystring=A) return(true); else return(false); ) boolIsOperator(charops)重載 ( if(ops=+110Ps=-110Ps=*110Ps=/110Ps=八|ops=( |ops=) return(true); else return(false); ) boolIsOperand(charch)/驗(yàn)證是否是數(shù) ( if(ch=0)&(chdata)&!IsOperator(prt-left_child-data)&!IsOperator(prt-right_child-data) ( floatnum

15、=0; floatnum1=atof(prt-left_child-data.c_str();/# data轉(zhuǎn)換成char型數(shù)據(jù)然后用atof將char轉(zhuǎn)換成浮點(diǎn)數(shù) floatnum2=atof(prt-right_child-data.c_str(); if(prt-data=+) num=num1+num2; elseif(prt-data=-) num=num1-num2; elseif(prt-data=*) num=num1*num2; elseif(prt-data=/) num=num1/num2; elseif(prt-data=A) num=pow(num1,num2); c

16、outnumt;/對(duì)每個(gè)結(jié)點(diǎn)計(jì)算后的中間結(jié)果 stringstreambob;/定義個(gè)流對(duì)象 bobdata=temp;/將計(jì)算的結(jié)果賦值給當(dāng)前結(jié)點(diǎn)prt-left_child=NULL;/然后刪除左右孩子結(jié)點(diǎn) prt-right_child=NULL; else if(prt-left_child=NULL&prt-right_child=NULL);如果左后孩子 都為空則不作操作 else evaluate(prt-left_child); evaluate(prt-right_child); evaluate(prt);/如果不滿(mǎn)足上面的條件則先 運(yùn)算左孩子再運(yùn)算右孩子再運(yùn)算本身

17、 /上述函數(shù)為一個(gè)遞歸調(diào)用即后序遍歷 /從根節(jié)點(diǎn)開(kāi)始計(jì)算如果子樹(shù)中不為空且不為數(shù)據(jù)則先 遍歷左子樹(shù)然后遍歷右子樹(shù)然后計(jì)算根節(jié)點(diǎn) ); /以上為二叉樹(shù)類(lèi)以及其中包含的功能函數(shù) node_type*build_node(stringx) 建立結(jié)點(diǎn)函數(shù)并將x存入結(jié)點(diǎn)的數(shù)據(jù)域里 ( node_type*new_node; new_node=newnode_type(x); return(new_node); )boolcalculator1(charOperatorA,charOperatorB) 判斷運(yùn)算符A和B優(yōu)先級(jí)是否相等 ( if(OperatorA=OperatorB|(OperatorA=

18、*&OperatorB=/ )|(OperatorA=/&OperatorB=*)|(OperatorA=+&Operator B=-)|(OperatorA=-&OperatorB=+) returntrue; else returnfalse; ) boolcalculator2(charOperatorA,charOperatorB)/判 別 符 號(hào) 的 優(yōu) 先 級(jí) 。AB,返 回 為T(mén)RUE,A=Bg回false if(OperatorA=() returnfalse; elseif(OperatorB=() returnfalse; elseif(Op

19、eratorB=) returntrue; elseif(calculator1(OperatorA,OperatorB) returnfalse; elseif(OperatorA=，A，) returntrue; elseif(OperatorB=A)returnfalse;elseif(OperatorA=*)|(OperatorA=/)returntrue; elseif(OperatorB=*)|(OperatorB=/)returnfalse; elseif(OperatorA=+)|(OperatorA=-)returntrue; else returnfalse; /采用了中序

20、遍歷的算法來(lái)將二叉樹(shù)r1拷貝到r2 boolisok(stringinfix)此函數(shù)驗(yàn)證式子是否正確，即是否 符合運(yùn)算規(guī)則。 chartemp;臨時(shí)字符變量 interror=0;/錯(cuò)誤標(biāo)記 intlb=0;左括號(hào)的個(gè)數(shù) intrb=0;/右括號(hào)的個(gè)數(shù) if(infix.size()=1&infix0!=-)/式子的長(zhǎng)度為1且第一個(gè) 為負(fù)號(hào) returnfalse; else if( ( IsOperator(infix0)&infix0!=-|/如果第一個(gè)是運(yùn) 算符且不為左括號(hào)則表達(dá)式錯(cuò)誤 IsOperator(infixinfix.size()-1)& infix0

21、!=(&infixinfix.size()-1!=)/如果最后一個(gè)字符 是運(yùn)算符且第一個(gè)和最后一個(gè)不是括號(hào)則表達(dá)式錯(cuò)誤 returnfalse; for(intm=0;minfix.size();m+) temp=infixm; if(m=0&temp=-&(isdigit(infix1)!=0| infix1=() temp=infix+m;/如果是負(fù)數(shù) if(IsOperand(temp); /如果是數(shù)字則不進(jìn)行操作 elseif(IsOperator(temp) ( if(temp=) ( rb+; if ( IsOperator(infixm+1)& (

22、infixm+1=+|infixm+1=-| infixm+1=*|infixm+1=/| infixm+1=A，|infixm+1=,) ) ( m+; if(infixm=)rb+; )else if(lsOperator(infixm+1) error+; elseif(temp=() ( lb+; if(infixm+1=() m+; lb+; else if(lsOperator(infixm+1)&infixm+1!=-) error+; else ( if(lsOperator(infixm+1)&infixm+1=() m+; lb+; ) else if(Is

23、Operator(infixm+1) error+; ) ) else error+; ) if(error=0&lb=rb)/如果沒(méi)有錯(cuò)誤且左右括號(hào)匹配 則返回邏輯真 return(true); else return(false); ) intmain() binary_treetree; stackNodeStack;/M算數(shù)棧 stackOpStack;/運(yùn)算符棧 stringinfix; charchoice=y; system(cls); charc; while(choice=y|choice=Y) ( coutinfix; cout n; cout”表達(dá)式為：infix

24、n; if(isok(infix) ( for(inti=0;iinfix.size();i+) ( c=infixi; if(i=0&c=-)/若開(kāi)始為負(fù)，則把零壓入運(yùn)算數(shù) 棧，把-壓入運(yùn)算符棧 ( binary_treetemp; temp.root=build_node(0); NodeStack.push(temp);將運(yùn)算數(shù)壓入數(shù)棧 OpStack.push(-);將運(yùn)算符壓入符棧 ) else if(IsOperand(c) ( stringtempstring; tempstring=c; while(i+1right_child=NodeStack.top().root; NodeStack.pop(); tree.root-left_child=NodeStack.top().root; NodeStack.pop(); NodeStack.push(tree); tree.root=NULL; OpStack.push(c); if(infixi+1=-) binary_treetemp; temp.root=build_node(0); NodeStack.push(temp); OpStack.push(-); +i; ) elseif(c=) ( while(OpStack.top()!=() ( OpStack.push(