算術表達式與二叉樹

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

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

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

4、始化，進棧與取棧頂元素操作進行對后綴表達式進行計算。 該模塊借助函數(shù) void InitStack(SeqStack *S) 初始化棧，int PushStack(SeqStack *S,char e)進棧，int GetTop(SeqStack3S,char *e)取棧頂元素，void TranslateExpress(char str,char exp) 中綴表達式轉后綴表達式，float ComputeExpress(char a)計算后綴表達式的值來實現(xiàn)；三、系統(tǒng)的設計與實現(xiàn)(一) 二叉樹的遍歷分析：首先構建一棵二叉樹，然后依次輸出每個遍歷的序列。流程圖如圖 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誨図后序遍何計貝結點如4char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree Create(BiTree T)/ 用擴展先序遍歷序列創(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é)點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)計葉結點的數(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( 請輸入二叉樹中的元素 ( 以擴展先序遍歷序列輸入 ):n);T=Create(T);printf( 先序遍歷序列為 :);Preorder(T);printf(n);printf( 中

9、序遍歷序列為 :);InOrder(T);printf(n);printf( 后序遍歷序列為 :);PostOrder(T);printf(n); sum=Sumleaf(T); printf( 葉結點的數(shù)目為 :%dn,sum);k=Depth(T);printf( 二叉樹的深度為 :%dn,k);6(二) 算術表達式求值分析：首先初始化一個棧，然后對相關的數(shù)據(jù)元素及運算符進棧，之后中綴表達式轉后綴表達式計算出后綴表達式的值。 流程圖如圖 3 所示。圖 3:算術表達式求值流程圖該模塊的具體代碼如下所示：#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)進棧if(S-top=MaxSize) pr

11、intf(”棧已滿，不能進棧 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; / 處理后進棧 else / 如果是運算符 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) /如果棧不空，將結果出棧并返回 result=S.dataS.top;S.top-; if(S.top=-1)return result;else printf(表達式錯誤);exit(-1); return 0; void mai n()char aMaxSize,bMaxSize;9float f;printf(請輸入一個算術表達式：”)；scan f(%s, &a);printf(中綴表達式為：sn,a);Tran slateExpress(a,b); printf(后綴表達式為：%sn,b);f=ComputeExpress(b);printf(計算結果：%fn ,f

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

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

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

18、ree Create(BiTree T)/用擴展先序遍歷序列創(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é)點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)計葉結點的

20、數(shù)目int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)/該結點的左或右分支為空時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)/進棧if(S-top=MaxSize) printf( 棧已滿，不能進棧 !);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+; /相當于一個循環(huán) , 把數(shù)組 a 值賦給 value.S.top+;S.dataS.top=value; / 處理后進棧 else / 如果是運算符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) / 如果棧不空，將結果出棧并返回 result=S.dataS.top;S.top-;if(S.top=-1) return result; else printf(表達式錯誤 );exit(-1); return 0; void main() BiTree T;int sum,k;printf( 請輸入二叉樹中的元素 ( 以擴展先序遍歷序列輸入T=Create(T);printf( 先序遍歷序列為 :); Preorder(T); pri