算術(shù)表達(dá)式與二叉樹

1、目錄一、系統(tǒng)開發(fā)的背景 .1.二、系統(tǒng)分析與設(shè)計(jì) .1.（一） 系統(tǒng)功能要求 .1.（二） 系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì) .1.三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) .3.（一） 二叉樹的遍歷 .3.（二） 算術(shù)表達(dá)式求值 .5.四、系統(tǒng)測試 .9.（一） 測試二叉樹遍歷函數(shù) .9.（二） 測試算術(shù)表達(dá)式求值函數(shù).1.0五、總結(jié).1.0.六、附件（代碼、部分圖表）.1.0（一） 程序代碼.1.0.（ 二） 實(shí)驗(yàn)截圖.1.5.1算術(shù)表達(dá)式與二叉樹一、系統(tǒng)開發(fā)的背景為了方便進(jìn)行基本的算術(shù)運(yùn)算，減輕對數(shù)字較大的數(shù)操作時(shí)所帶來的 麻煩，及其在運(yùn)算過程中錯(cuò)誤的避免。因此設(shè)計(jì)算術(shù)表達(dá)式與二叉樹的程 序來解決此問題。二、系統(tǒng)分析與設(shè)計(jì)

2、（一）系統(tǒng)功能要求由于一個(gè)表達(dá)式和一棵二叉樹之間，存在著自然的對應(yīng)關(guān)系。遍寫一個(gè)程序，實(shí)現(xiàn)基于二叉樹表示的算術(shù)表達(dá)式的操作。算術(shù)表達(dá)式 內(nèi)可以含有變量（az）、常量（09）和二元運(yùn)算符（+, -, * , /,A（乘幕） 。具體實(shí)現(xiàn)以下操作：1 以字符序列的形式輸入語法正確的前綴表達(dá)式并構(gòu)造表達(dá)式。2 用帶括弧的中綴表達(dá)式輸出表達(dá)式。3 實(shí)現(xiàn)對變量 V 的賦值（V=c）,變量的初值為 0。4 對算術(shù)表達(dá)式 E 求值。（二） 系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)通過對系統(tǒng)功能的分析，基于二叉樹表示的算術(shù)表達(dá)式的功能 如圖（ 1）所示。2圖 1 基于二叉樹表示的算術(shù)表達(dá)式的功能圖通過上圖的功能分析，把整個(gè)系統(tǒng)劃分為主

3、要的兩大個(gè)模塊：1、 將語法正確的前綴表達(dá)式用二叉樹的遍歷轉(zhuǎn)換成相應(yīng)的遍歷序列，必要時(shí)可以求出此二叉樹的結(jié)點(diǎn)數(shù)及其樹的深度。該模塊借助函數(shù)BiTreeCreate(BiTree T)創(chuàng)建二叉樹，void Preorder(BiTree T)先序遍歷，voidInOrder(BiTree T)中序遍歷，void PostOrder(BiTree T)后序遍歷，intSumleaf(BiTree T) 統(tǒng)計(jì)葉結(jié)點(diǎn)的數(shù)目，int Depth(BiTree T)二叉樹的深 度 6 個(gè)函數(shù)聯(lián)合來實(shí)現(xiàn)；2、 計(jì)算中序遍歷所得的算術(shù)表達(dá)式的值。其中先要將掃描得到的中綴 表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后利用棧的初

4、始化，進(jìn)棧與取棧頂元素操作進(jìn)行對后綴表達(dá)式進(jìn)行計(jì)算。 該模塊借助函數(shù) void InitStack(SeqStack *S) 初始化棧，int PushStack(SeqStack *S,char e)進(jìn)棧，int GetTop(SeqStack3S,char *e)取棧頂元素，void TranslateExpress(char str,char exp) 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，float ComputeExpress(char a)計(jì)算后綴表達(dá)式的值來實(shí)現(xiàn)；三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)(一) 二叉樹的遍歷分析：首先構(gòu)建一棵二叉樹，然后依次輸出每個(gè)遍歷的序列。流程圖如圖 2 所示。二叉樹的遍歷圖

5、2:二叉樹的遍歷流程圖該模塊的具體代碼如下所示：#in clude#in clude#define MaxSize 50typedef struct float dataMaxSize;int top;OpStack;typedef structchar dataMaxSize;int top;SeqStack;typedef struct BiTNodeffiB誨図后序遍何計(jì)貝結(jié)點(diǎn)如4char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree Create(BiTree T)/ 用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹 char ch;

6、ch=getchar(); if(ch=0)T=NULL;else T=new BiTNode;T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild); return T; void Visit(char ch)/ 訪問根節(jié)點(diǎn)Visit(T-data);int Sumleaf(BiTree T)/ int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)/sum+;m=Sumleaf(T-lchild);sum=sum+m;n=Sumleaf(T-rchild);sum=sum+n;re

7、turn sum; printf(%c ,ch);void Preorder(BiTree T)/ if(T=NULL) return;Visit(T-data);Preorder(T-lchild);Preorder(T-rchild);void InOrder(BiTree T)/ if(T=NULL)return;InOrder(T-lchild);Visit(T-data);InOrder(T-rchild);void PostOrder(BiTree T)/if(T=NULL)return;PostOrder(T-lchild);PostOrder(T-rchild);先序遍歷中序遍

8、歷后序遍歷統(tǒng)計(jì)葉結(jié)點(diǎn)的數(shù)目該結(jié)點(diǎn)的左或右分支為空時(shí)5int Depth(BiTree T)/二叉樹的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild); depr=Depth(T-rchild);dep=1+(depldepr?depl:depr);return dep;void main()BiTree T;int sum,k;printf( 請輸入二叉樹中的元素 ( 以擴(kuò)展先序遍歷序列輸入 ):n);T=Create(T);printf( 先序遍歷序列為 :);Preorder(T);printf(n);printf( 中

9、序遍歷序列為 :);InOrder(T);printf(n);printf( 后序遍歷序列為 :);PostOrder(T);printf(n); sum=Sumleaf(T); printf( 葉結(jié)點(diǎn)的數(shù)目為 :%dn,sum);k=Depth(T);printf( 二叉樹的深度為 :%dn,k);6(二) 算術(shù)表達(dá)式求值分析：首先初始化一個(gè)棧，然后對相關(guān)的數(shù)據(jù)元素及運(yùn)算符進(jìn)棧，之后中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式計(jì)算出后綴表達(dá)式的值。 流程圖如圖 3 所示。圖 3:算術(shù)表達(dá)式求值流程圖該模塊的具體代碼如下所示：#in clude#in clude#in clude#in clude#in clude

10、#define NULL 0#define MaxSize 50typedef struct float dataMaxSize;int top;OpStack;typedef structchar dataMaxSize;int top;SeqStack;void In itStack(SeqStack *S)初始化棧 S-top=0; 7int StackEmpty(SeqStack S)/ 判斷棧是否為空 if(S.top =0) return 1;else return 0; int PushStack(SeqStack *S,char e)進(jìn)棧if(S-top=MaxSize) pr

11、intf(”棧已滿，不能進(jìn)棧 r);return 0; else S-dataS-top=e;S-top+;return 1; int PopStack(SeqStack *S,char *e)/ 刪除棧頂元素 if(S-top=0) printf( 棧已空 n);return 0; else S-top-;*e=S-dataS-top;return 1; int GetTop(SeqStack S,char *e)/ 取棧頂元素 if(S.top=0&ch=0&ai=9)/ 如果是數(shù)字 value=0;while(ai!= ) /如果不是空格 value=10*value+a

12、i-0;i+; S.top+;S.dataS.top=value; / 處理后進(jìn)棧 else / 如果是運(yùn)算符 switch(ai) case+: x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-;result=x1+x2; S.top+; S.dataS.top=result; break; case-: x1=S.dataS.top; S.top-;x2=S.dataS.top; S.top-; result=x2-x1; S.top+; S.dataS.top=result; break; case*: x1=S.dataS.top;S.top

13、-; x2=S.dataS.top; S.top-; result=x1*x2; S.top+;S.dataS.top=result; break;case/:x 仁 S.dataS.top; S.top-;x2=S.dataS.top; S.top-;result=x2/x1; S.top+;S.dataS.top=result; break;caseA:x 仁 S.dataS.top; S.top-;x2=S.dataS.top; S.top-;result=float(pow(x1,x2); S.top+;S.dataS.top=result; break; i+;if( S.top !

14、=-1) /如果棧不空，將結(jié)果出棧并返回 result=S.dataS.top;S.top-; if(S.top=-1)return result;else printf(表達(dá)式錯(cuò)誤);exit(-1); return 0; void mai n()char aMaxSize,bMaxSize;9float f;printf(請輸入一個(gè)算術(shù)表達(dá)式：”)；scan f(%s, &a);printf(中綴表達(dá)式為：sn,a);Tran slateExpress(a,b); printf(后綴表達(dá)式為：%sn,b);f=ComputeExpress(b);printf(計(jì)算結(jié)果：%fn ,f

15、);四、系統(tǒng)測試（一）測試二叉樹遍歷函數(shù)：測試的結(jié)果如圖 4圖 4：二叉樹的遍歷concinue請輸叉樹中的元素C臥擴(kuò)展先序遍歷序列輸入”& &3 32 2e e 2 23 32 2131310（二） 測試算術(shù)表達(dá)式求值函數(shù)：測試的結(jié)果如圖 5, 6C:USER5AC:USER5A DMINISTRATQRDESiaOPDMINISTRATQRDESiaOP ff文件烹gbuggbug莒術(shù)表達(dá)式我值啟灼.昇術(shù)表達(dá)貳：42-142-1為匸/3/3為：4 4 2 2 11 -3-3 / /tQcon七iinii呂.圖 6五、總結(jié)系統(tǒng)完成了對基本的數(shù)學(xué)算術(shù)運(yùn)算的求值的功能。系統(tǒng)不能對

16、更高一級的復(fù)合表達(dá)式（如三角函數(shù)等）求值，是其不足 之處。我的收獲是經(jīng)過不斷的查詢相關(guān)的書籍與有關(guān)的資料，使得我對原本 不熟的知識有了深刻的了解和認(rèn)識。也讓我能夠更加獨(dú)立的去學(xué)習(xí)，提高 了我的自主學(xué)習(xí)的能力。六、附件（代碼、部分圖表）（一）程序代碼：#i nclude#i nclude字符串函數(shù)#in clude功能：分配字節(jié)的存儲(chǔ)區(qū)，若內(nèi)存不夠返回0.#i nclude/ta ndard library標(biāo)準(zhǔn)庫函數(shù)頭文件，stdlib.h里面定義了五種類型、一些宏和通用工具函數(shù)#i nclude數(shù)學(xué)庫函數(shù)#define NULL 0#define MaxSize 50Ass壬帛后計(jì)一工- -X

17、 X : :y y一達(dá)達(dá)果a an nCUS/口瀝8 85 5 2 2箱 T /訐算結(jié)果：2.000000PressPress負(fù)nyny keke coco contcont inue_inue_11typedef struct float dataMaxSize;12int top;OpStack;/ 存放數(shù)字的棧typedef structchar dataMaxSize;int top;SeqStack;/ 存放運(yùn)算符的棧 typedef struct BiTNode char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiT

18、ree Create(BiTree T)/用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹 char ch;ch=getchar(); if(ch=0) T=NULL;else T=new BiTNode; T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild); return T;void Visit(char ch)/訪問根節(jié)點(diǎn)sum+; m=Sumleaf(T-lchild);sum=sum+m; n=Sumleaf(T-rchild);sum=sum+n; printf(%c ,ch); voidPreorder(BiTree T)/ i

19、f(T=NULL) return;Visit(T-data);Preorder(T-lchild);Preorder(T-rchild);void InOrder(BiTree T)/ if(T=NULL) return;InOrder(T-lchild);Visit(T-data);InOrder(T-rchild); voidPostOrder(BiTree T)/ if(T=NULL) return;PostOrder(T-lchild);PostOrder(T-rchild);Visit(T-data); 先序遍歷中序遍歷后序遍歷int Sumleaf(BiTree T)/統(tǒng)計(jì)葉結(jié)點(diǎn)的

20、數(shù)目int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)/該結(jié)點(diǎn)的左或右分支為空時(shí)13return sum;int Depth(BiTree T)/二叉樹的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild);depr=Depth(T-rchild); dep=1+(depldepr?depl:depr); return dep;void InitStack(SeqStack *S)/初始化棧 S-top=0; int StackEmpty(SeqStack S)/判斷棧是否為空 if

21、(S.top =0) return 1;else return 0; int PushStack(SeqStack *S,char e)/進(jìn)棧if(S-top=MaxSize) printf( 棧已滿，不能進(jìn)棧 !);return 0; else S-dataS-top=e;S-top+;return 1; int PopStack(SeqStack *S,char *e)/刪除棧頂元素 if(S-top=0) printf( 棧已空 n);return 0; elseS-top-; *e=S-dataS-top;return 1; int GetTop(SeqStack S,char *e)

22、/取棧頂元素 if(S.top=0&ch=0&ai=9)/如果是數(shù)字 value=0; while(ai!= ) /如果不是空格 value=10*value+ai-0; i+; /相當(dāng)于一個(gè)循環(huán) , 把數(shù)組 a 值賦給 value.S.top+;S.dataS.top=value; / 處理后進(jìn)棧 else / 如果是運(yùn)算符switch(ai)case+:x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-;result=x1+x2; S.top+;S.dataS.top=result; break;case-:x1=S.dataS.t

23、op;S.top-; x2=S.dataS.top; S.top-;result=x2-x1; S.top+;S.dataS.top=result; break; case*:x1=S.dataS.top;S.top-; x2=S.dataS.top; S.top-;result=x1*x2;S.top+; S.dataS.top=result; break;case/: x1=S.dataS.top; S.top-; x2=S.dataS.top; S.top-; result=x2/x1; S.top+;S.dataS.top=result; break;case:x1=S.dataS.t

24、op; S.top-; x2=S.dataS.top; S.top-; result=float(pow(x1,x2); S.top+;15S.dataS.top=result; break; i+; if( S.top !=-1) / 如果棧不空，將結(jié)果出棧并返回 result=S.dataS.top;S.top-;if(S.top=-1) return result; else printf(表達(dá)式錯(cuò)誤 );exit(-1); return 0; void main() BiTree T;int sum,k;printf( 請輸入二叉樹中的元素 ( 以擴(kuò)展先序遍歷序列輸入T=Create(T);printf( 先序遍歷序列為 :); Preorder(T); pri