表達式類型的實現

1、*理工大學數據結構課程設計報告題目：表達式類型的實現 院（系）：計算機工程學院 學生姓名: * 班級： 計算111 學號:2011070*起迄日期: 2012.7.82012.7.19 指導教師: * 一、需求分析1.問題描述：本程序通過輸入前綴表達式建立一顆二叉樹，通過中序遍歷建立好的二叉樹輸出帶括號的中綴表達式。然后中序遍歷二叉樹對表達式中的未知數x進行賦值。通過后序遍歷二叉樹計算表達式的值。根據兩顆二叉樹和輸入的運算符構造復合表達式。另外，通過中序遍歷二叉樹對表達式進行化簡。 2.基本功能以字符序列的形式輸入語法正確的前綴表示式并構成表達式E用帶括號的中綴表達式輸出表達式E實現對變量x的

2、賦值，變量初始值為0對算術表達式求值構造新的復合表達式（E1）P（E2）對表達式進行化簡 3.輸入輸出本程序運算數的輸入輸出局限于無符號整型數據，運算符的輸入輸出包括“+、-、*、/、”二、 概要設計1.設計思路：本程序以字符序列的形式輸入語法正確的前綴表達式，在輸入表達式的過程中判斷輸入的字符是運算數還是運算符并將其保存到樹節(jié)點中相應的位置，表達式輸入結束的同時也就構成一顆二叉樹。根據建立好的二叉樹，可以采用中序遍歷二叉樹的方法輸出正常順序的表達式。在中序遍歷二叉樹時，訪問存放運算符的結點時要判斷其與雙親結點中運算符的優(yōu)先級關系來判斷是否要添加括號。在給表達式中的未知數x賦值時，本程序采用的

3、是中序遍歷二叉樹的方法，遇到存放x的結點就將數值賦值給其數據域的變量。然后通過后序遍歷二叉樹的方法就行表達式求值。構造復合表達式可以分別建立兩顆二叉樹，然后將這兩顆二叉樹作為新申請的運算符結點的左右孩子結點。在化簡表達式時，先判斷運算符結點的兩個孩子節(jié)點是不是運算數結點（不包括x結點）。如果兩個孩子節(jié)點是運算數結點，就計算出這個子表達式的值并用其代替這個運算符結點。 2.數據結構設計：抽象數據類型二叉樹的定義如下：ADT BinaryTree 數據對象D：D是具有相同特性的數據元素的集合。數據關系R：若D=，則R=，稱BinaryTree為空二叉樹；若D，則R=H，H是如下二元關系：（1）在D

4、中存在唯一的稱為根的數據元素root，它在關系H下無前驅；（2）若D-root，則存在D_root=D1,Dr,且D1Dr=；（3）若D1，則D1中存在唯一的元素X1，<root，X1>H，且存在D1上的關系H1H；若Dr，則Dr中存在唯一的元素Xr，<root,Xr>H,且存在Dr上的關系HrH；H=<root,X1>,<root,Xr>,H1,Hr；（4）（D1，H1）是一顆符合本定義的二叉樹，稱為根的左子樹，（Dr，Hr）是一顆符合本定義的二叉樹，稱為根的右子樹?；静僮鳎篊reatBitTree (BitTree T,BitTree p)

5、;操作結果：根據前綴表達式先序構造二叉樹。InOrderTraverse(BitTree T)初始條件：二叉樹T存在。操作結果：中序遍歷二叉樹T，輸出每個結點的數據域且僅一次。InOrder(BitTree T,int *num);初始條件：二叉樹T存在且存在x結點。操作結果：將num賦值給x。PostOrderTraverse(BitTree T);初始條件：二叉樹T。操作結果：后序遍歷二叉樹求表達式的值。ADT BinaryTree3.軟件結構設計：BitTree ReadExpr(BitTree T);BitTree WriteExpr(BitTree T)BitTree Assign(

6、BitTree T);BitTree Value(BitTree T);Int main（）Void menu（）void CompoundExpr(BitTree T);void MergeConstruction(BitTree T);退出！三、 詳細設計 1. 定義程序中所有用到的數據及其數據結構，及其基本操作的實現；typedef struct BitNodechar data;int opnd;struct BitNode *lchild;struct BitNode *rchild;struct BitNode *parent;BitNode,*BitTree;2主函數和其他函數的

7、偽碼算法；(1)主函數：int main()BitTree T=NULL;T=(BitTree )malloc(sizeof(BitNode); if(T=NULL)printf("有錯n");elseflag=0;menu(T);return 0;(2) 菜單函數：void menu(BitTree T)int sel=0;doprintf("nn");printf(" (1) 以字符序列的形式輸入語法正確的前綴表示式并構造表達式 n");printf(" (2) 用帶括弧的中綴表達式輸出表達式 n");prin

8、tf(" (3) 實現對變量x的賦值（x=c）,變量的初值為0 n");printf(" (4) 對算術表達式求值 n");printf(" (5) 造一個新的復合表達式（E1）P(E2) n");printf(" (6) 表達式化簡n");printf(" (0) 退出 n");printf(" 請輸入您的選擇:");scanf("%d",&sel);printf("%d",sel);system("cls"

9、;);switch(sel)case 1: T=ReadExpr(T);break;case 2: T=WriteExpr(T);break;case 3: T=Assign(T);break;case 4: T=Value(T);break;case 5: CompoundExpr(T);break;case 6: MergeConstruction(T);break;case 0: printf(" 已退出!n");break;while(sel!=0);(3) 構建二叉樹函數：BitTree CreatBitTree (BitTree T,BitTree p) cha

10、r ch;ch=getche();if(In(ch)=0)printf("n表達式有誤,請重新輸入:n");T = CreatBitTree (T,p);return T;T=(BitTree )malloc(sizeof(BitNode); if(T=NULL)printf("有錯n");elseif(In(ch)=2)if(ch='x')xflag=1;assg=0;T->data = ch;T->opnd = 0;elseT->data = 'N'T->opnd = ch-'0'

11、;else if(In(ch)=1)T->data = ch;T->opnd = 0;T->parent = p; p=T; if(In(ch)=2) T->lchild = NULL;T->rchild = NULL; else if(In(ch)=3) T->lchild = CreatBitTree(T->lchild ,p );T->rchild = NULL; else T->lchild = CreatBitTree(T->lchild ,p ); T->rchild = CreatBitTree(T->rch

12、ild ,p ); return T;(4) 中序遍歷二叉樹輸出帶括號中綴表達式的函數：void InOrderTraverse(BitTree T)if(T=NULL)return ;else if(Precede(T->data , T->parent->data )=-1) printf("(");InOrderTraverse(T->lchild);if(T->data = 'N')printf("%d",T->opnd);else printf("%c",T->dat

13、a); InOrderTraverse(T->rchild); printf(")");elseInOrderTraverse(T->lchild); if(T->data = 'N')printf("%d",T->opnd);else printf("%c",T->data); InOrderTraverse(T->rchild); (5) 中序遍歷二叉樹給變量x賦值的函數：void InOrder(BitTree T,int *num)if(T=NULL)return; else

14、 if(Precede(T->data , T->parent->data )=-1) printf("(");InOrder(T->lchild,num); if(T->data = 'N')printf("%d",T->opnd);else if(T->data = 'x')T->opnd = *num;printf("%d",T->opnd );else printf("%c",T->data);InOrder(T-&

15、gt;rchild,num); printf(")");elseInOrder(T->lchild,num); if(T->data = 'N')printf("%d",T->opnd);else if(T->data = 'x')T->opnd = *num;printf("%d",T->opnd );else printf("%c",T->data);InOrder(T->rchild,num); (6) 后序遍歷二叉樹求表達式值的

16、函數：void PostOrderTraverse(BitTree T)if(T=NULL)return; else PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild);if(In(T->data )=2)return;else if(In(T->data )=1)T->opnd = calculate(T->lchild ->opnd ,T->data ,T->rchild ->opnd ); (7) 構造復合表達式的函數：void CompoundExpr(BitT

17、ree T)char optr;BitTree T1=NULL,T2=NULL;BitTree p;p=T1;printf("請以字符序列的形式輸入語法正確的前綴表示式E1:n");T1=CreatBitTree (T1,p);T1->parent = T1; printf("n二叉樹構造成功!n");p=T2;printf("請以字符序列的形式輸入語法正確的前綴表示式E2:n");T2=CreatBitTree (T2,p);T2->parent = T2; printf("n二叉樹構造成功!n");

18、printf("請輸入運算符p:");getchar();scanf("%c",&optr);T->data = optr;T->opnd = 0;T->parent = T;T->lchild = T1;T->rchild = T2;T1->parent = T;T2->parent = T;flag=1;(8) 化簡函數表達式的函數：void MergeConstruction(BitTree T)int a=1;printf("化簡后表達式為: ");while(a=1)a=0;

19、huajian(T,&a);InOrderTraverse(T);printf("n");void huajian(BitTree T,int *a)if(T=NULL)return; else huajian(T->lchild,a); if(In(T->data )=1&&T->lchild ->data = 'N'&&T->rchild ->data = 'N')T->opnd = calculate(T->lchild ->opnd ,T-&

20、gt;data ,T->rchild ->opnd );T->data = 'N'T->lchild = NULL;T->rchild = NULL;*a=1;huajian(T->rchild,a); 開始3. 主要函數的程序流程圖，實現設計中主程序和其他子模塊的算法，以流程圖的形式表示。輸入選項yesCreatBitTree (BitTree T,BitTree p)ReadExpr(T);選項1noInOrderTraverse(BitTree T)yesWriteExpr(BitTree T)選項2noyesInOrder(BitTr

21、eeT,int *num)Assign(BitTree T)選項3noyesPostOrderTraverse(BitTree T)Value(BitTree T)選項4noyesCreatBitTree (BitTree T,BitTree p) CompoundExr(BitTree T)選項5noyesHuajian(BitTree T,int *a)MergeConstruction(BitTreeT)選項6noyes選項0no結束4. 畫出函數之間的調用關系圖。BitTree ReadExpr(BitTree T);CreatBitTree (BitTree T,BitTree p)

22、BitTree WriteExpr(BitTree T)InOrderTraverse(BitTree T)BitTree Assign(BitTree T);InOrder(BitTreeT,int *num)Void menu（）Int main（）BitTree Value(BitTree T);PostOrderTraverse(BitTree T)void CompoundExpr(BitTree T);CreatBitTree (BitTree T,BitTree p) void MergeConstruction(BitTree T);Huajian(BitTree T,int

23、*a)四、 調試分析 1. 實際完成的情況說明（完成的功能，支持的數據類型等）；（1）以字符序列的形式輸入正確的前綴表達式。（2）用帶括號的中綴表達式輸出表達式。（3）實現對變量x的賦值，初始值為0。（4）對算術表達式求值。（5）構造新的復合表達式。（6) 對表達式化簡。 2.程序的性能分析，包括時空分析；本程序實現了通過遍歷二叉樹對表達式的求值，化簡等操作。此外，可以增加一些其他的操作或者增加一些其他的運算操作。 3.上機過程中出現的問題及其解決方案；（1） 構建的二叉樹為空。解決方案：通過傳地址的方式調用二叉樹操作函數。（2） 運行程序是無法輸入字符。解決方案：用ch=getche();語

24、句接收字符。（3） 使用數學函數時出錯。解決方案：添加頭文件#include <math.h>。4. 程序中可以改進的地方說明；本程序運算數的輸入輸出局限于無符號整型數據，運算符的輸入輸出包括“+、-、*、/、”。可以通過改進實現對浮點型數據的計算。另外，可以增加一些其他的運算，例如三角函數，指數函數等等。5. 程序中可以擴充的功能及設計實現假想。程序可以增加對操作符sin，cos，tan，cot，log，ln等運算符的識別，也可以增加對浮點型數據的操作的功能。五、測試結果（1）構建二叉樹（2）輸出帶括號的中綴表達式：（3）對變量x賦值：（4）對算術表達式求值：（5）構造復合表達式：（6）化簡表達式：（7）錯誤提示：六、用戶手冊第一步：輸入選項一，構建二叉樹。如下圖：第二步：輸入前綴表達式：第三步：輸入選項二，輸出