實(shí)驗(yàn)三實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)三實(shí)驗(yàn)報(bào)告1120131317 周任然1、簡(jiǎn)易計(jì)算器（1）問題描述由鍵盤輸入一算術(shù)表達(dá)式，以中綴形式輸入，試編寫程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換成一棵二叉表達(dá)式樹，通過對(duì)該的后序遍歷求出計(jì)算表達(dá)式的值。（2）基本要求 a要求對(duì)輸入的表達(dá)式能判斷出是否合法。不合法要有錯(cuò)誤提示信息。b將中綴表達(dá)式轉(zhuǎn)換成二叉表達(dá)式樹。c后序遍歷求出表達(dá)式的值（3）數(shù)據(jù)結(jié)構(gòu)與算法分析一棵表達(dá)式樹，它的樹葉是操作數(shù)，如常量或變量名字，而其他的結(jié)點(diǎn)為操作符。a建立表達(dá)式樹。二叉樹的存儲(chǔ)可以用順序存儲(chǔ)也可用鏈?zhǔn)酱鎯?chǔ)。當(dāng)要?jiǎng)?chuàng)建二叉樹時(shí)，先從表達(dá)式尾部向前搜索，找到第一個(gè)優(yōu)先級(jí)最低的運(yùn)算符，建立以這個(gè)運(yùn)算符為數(shù)據(jù)元素的根結(jié)點(diǎn)。注意到表

2、達(dá)式中此運(yùn)算符的左邊部分對(duì)應(yīng)的二叉绔為根結(jié)點(diǎn)的左子樹，右邊部分對(duì)應(yīng)的是二叉绔為根結(jié)點(diǎn)的右子樹，根據(jù)地這一點(diǎn)，可用遞歸調(diào)用自己來完成對(duì)左右子樹的構(gòu)造。b求表達(dá)式的值。求值時(shí)同樣可以采用遞歸的思想，對(duì)表達(dá)式進(jìn)行后序遍歷。先遞歸調(diào)用自己計(jì)算左子樹所代表的表達(dá)式的值，再遞歸調(diào)用自己計(jì)算右子樹代表的表達(dá)式的值，最后讀取根結(jié)點(diǎn)中的運(yùn)算符，以剛才得到的左右子樹的結(jié)果作為操作數(shù)加以計(jì)算，得到最終結(jié)果。（4）需求分析程序運(yùn)行后顯示提示信息，輸入任意四則運(yùn)算表達(dá)式，倘若所輸入的表達(dá)式不合法程序?qū)?bào)錯(cuò)。輸入四則運(yùn)算表達(dá)式完畢，程序?qū)⑤敵鲞\(yùn)算結(jié)果。測(cè)試用的表達(dá)式須是由+、-、*、/運(yùn)算符，括號(hào)“(”、“)”與相應(yīng)的運(yùn)

3、算數(shù)組成。運(yùn)算數(shù)可以是無符號(hào)浮點(diǎn)型或整型，范圍在065535。（5）概要設(shè)計(jì)二叉樹的抽象數(shù)據(jù)類型定義ADT BinaryTree 數(shù)據(jù)對(duì)象：表達(dá)式運(yùn)算數(shù) num | 0< num < 65535 表達(dá)式運(yùn)算符 opr | + , - , * , / 數(shù)據(jù)關(guān)系：由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成，且樹中結(jié)點(diǎn)具有層次關(guān)系。根結(jié)點(diǎn)必須為運(yùn)算符，葉子結(jié)點(diǎn)必須為運(yùn)算數(shù)?；静僮鳎?InitBiTree(&T , &S) 初始條件：存在一四則運(yùn)算前綴表達(dá)式S。 操作結(jié)果：根據(jù)前綴表達(dá)式S構(gòu)造相應(yīng)的二叉樹T。 DestroyBiTree(&T) 初始條件：二叉樹T已

4、經(jīng)存在。 操作結(jié)果：銷毀T。 Value(&T) 初始條件：二叉樹T已經(jīng)存在。 操作結(jié)果：計(jì)算出T所表示的四則運(yùn)算表達(dá)式的值并返回。ADT BineryTree順序棧的抽象數(shù)據(jù)類型定義ADT Stack 數(shù)據(jù)對(duì)象：具有相同類型及后進(jìn)先出特性的數(shù)據(jù)元素集合。 數(shù)據(jù)關(guān)系：相鄰數(shù)據(jù)元素具有前去和后繼關(guān)系。 基本操作： InitStack(&S) 初始條件：無 操作結(jié)果：構(gòu)造一個(gè)空棧S。 DestroyStack(&S) 初始條件：棧S已經(jīng)存在。 操作結(jié)果：銷毀S。 StackLength(&S) 初始條件：棧S已經(jīng)存在。 操作結(jié)果：返回S中元素個(gè)數(shù)。 GetTop(S

5、 , &e) 初始條件：棧S已經(jīng)存在且非空。 操作結(jié)果：用e返回S的棧頂元素。 Push(&S , e) 初始條件：棧S已經(jīng)存在。 操作結(jié)果：插入元素e為S的新棧頂元素。 Pop(&S , e) 初始條件：棧S已經(jīng)存在且非空。 操作結(jié)果：刪除S的棧頂元素，并用e返回其值。ADT Stack字符串的抽象數(shù)據(jù)類型定義ADT String 數(shù)據(jù)對(duì)象：具有字符類型的數(shù)據(jù)元素集合。 數(shù)據(jù)關(guān)系：相鄰數(shù)據(jù)元素具有前驅(qū)和后繼關(guān)系。 基本操作： StrLength(S) 初始條件：串S已經(jīng)存在。 操作結(jié)果：返回S的元素個(gè)數(shù)。 StrNeg(S , F) 初始條件：串S已經(jīng)存在且非空。 操

6、作結(jié)果：求S的逆序并將結(jié)果保存在串F中。ADT String本程序包含四個(gè)模塊：主程序模塊；二叉樹單元模塊（實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型，包括結(jié)點(diǎn)和指針的定義）；順序棧單元模塊（實(shí)現(xiàn)順序棧的抽象數(shù)據(jù)類型，包含結(jié)點(diǎn)和指針的定義）；字符串單元模塊(實(shí)現(xiàn)字符串的抽象數(shù)據(jù)類型)。四個(gè)模塊之間調(diào)用關(guān)系為主程序模塊二叉樹模塊，二叉樹模塊調(diào)用順序棧模塊。詳細(xì)設(shè)計(jì)順序棧類型。#define Stack_Size 100typedef struct char elemStack_Size; int top;SqStack 基本操作實(shí)現(xiàn)的偽代碼算法如下： void InitStack (SqStack &S)

7、 /初始化順序棧 S.elem=new ElemTypeStack_Size; if(!S.elem) Error("Overflow!"); S.top=-1; viod Push (SqStack &S,char c) /順序棧壓棧 if(S.top=(Stack_Size-1) Error("Stack Overflow!"); S.elem+S.top=c; ElemType Pop (SqStack &S) /順序棧出棧 if(S.top=-1) Error("Stack Empty!"); return S

8、.elemS.top-; int StackLength(SqStack &S) /求順序棧長(zhǎng)度 return (S.top+1); GetTop(SqStack &S ,char e) /取棧頂元素 e=S.elemtop; 字符串類型typedef struct /動(dòng)態(tài)順序串 char *ch; int length;String基本操作實(shí)現(xiàn)的偽代碼算法如下：int StrLength(&S) /求串長(zhǎng) return S.length; void StrNeg(&S , &F) /求逆序串if(!S.length) error(“String Emp

9、ty!”); for(i=0 ; i<length ; i+) F.chi = S.chlength-1-i; 二叉樹類型。typedef struct TNode /二叉樹結(jié)點(diǎn) union data char optr; /運(yùn)算符 int opnd; ; /操作數(shù) struct TNode *lchild , *rchildTNodetypedef TNode *BiTree /二叉樹指針 基本操作實(shí)現(xiàn)的偽代碼算法如下：int Precedence (char opr) /判斷運(yùn)算符級(jí)別函數(shù)；其中* /的級(jí)別為2，+ -的級(jí)別為1；int level; switch(opr) case

10、'+': case'-': return (1); break; case'*': case'/': return(2); break; case'(': case')': case'#': default:return(0); break; bool IsOperator(char opr) /判斷輸入串中的字符是不是合法操作符if(op='+'|op='-'|op='*'|op='/') return true; e

11、lse return false; string Convert(string &Str) /將一個(gè)中綴串轉(zhuǎn)換為后綴串，string Output; /輸出串SqStack S; for(int i=S.length-1 ; i>=0 ; i-) /對(duì)輸入串逆序掃描 if(Str.chi>=48&&Str.chi<=57) Output.chi=Str.chi; /假如是操作數(shù)，把它添加到輸出串中。 Output.length+; if( Str.chi=')' ) /假如是右括號(hào)，將它壓棧。Push( S , Str.chi ); w

12、hile( IsOperator( si ) ) /如果是運(yùn)算符 if( top=0 | GetTop(S)=')' | Precedence(Str.chi ) >=Precedence( GetTop(S) ) ) Push( S , Str.chi ); break; else Pop(S , e); Output.chi=e; Output.length+; if( Str.chi='(' ) /假如是左括號(hào)，棧中運(yùn)算符逐個(gè)出棧并輸出，直到遇到右括號(hào)。右括號(hào)出棧并丟棄。 while( GetTop(S)!=')' ) Output.

13、chi=Pop(S); Output.length+; while(S.top!=-1) /假如輸入完畢，棧中剩余的所有操作符出棧并加到輸出串中。 Output.ch=Output.ch-; Output.ch=Pop(S); return output;void CreatBiTree(&T , &S) /由中綴表達(dá)式生成表達(dá)式二叉樹 String F; SqStack Sq; /用以存放生成的二叉樹結(jié)點(diǎn) InitStack(Sq); F=Convert(S); /求得S的前綴表達(dá)式 for(i=F.length-1 ; i>=0 ; i-) If( !IsOperat

14、or(F.chi) ) T=new TNode; T->data=F.chi; T->lchild=NULL; T->rchild=NULL; Push(Sq , T) else T=new TNode; T->data=F.chi; T->lchild=Pop( Sq ); T->rchild=Pop( Sq ); Push(Sq , T); int Calc(int a, char opr, int b) /計(jì)算 switch (opr) case '+': return a + b; case '-': return a

15、 - b; case '*': return a * b; case '/': return a / b; int Value(TNode *T) if (T->lchild = NULL &&T->rchild = NULL) return T->data; else return Calc( Value(T->lchild) , T->data , Value(T->rchild) );主函數(shù)偽碼算法。void main() Face(); /輸出界面及相關(guān)信息 do cout<<”Please

16、 input an expression:”<<endl; cin>>Str; JudgeExp(S); /判斷輸入的表達(dá)式是否合法。 T=CreatBiTree(S);N=Value(T); cout<<”The value of this expression is”<<N<<endl;cout<<”To do another calculation? Y/N” ;cin>>e; if(e=y) flag=1;else flag=0; while(flag) /main測(cè)試結(jié)果附錄（帶注釋的源程序）/*CS

17、tack.h*/#include<iostream>using namespace std;#define Stack_Size 100typedef struct /字符類型順序棧 char elemStack_Size; int top;CStackvoid InitCStack(&S) /初始化順序棧 S.elem=new charStack_Size; if(!S.elem) Error("Overflow!"); S.top=-1;void Push_C(CStack &S , char e) /壓棧 if( S.top=(Stack_

18、Size-1) ) Error("Stack Overflow!"); S.elem+S.top=e;char Pop_C(CStack &S) /出棧 if(S.top=-1) Error("Stack Empty!"); return S.elemtop-;char GetTop(&S) /取棧頂元素 if(S.top=-1) Error("Stack Empty!"); return S.elemtop;int CStackLength(&S) /求棧中元素個(gè)數(shù) return top+1;/*TStack

19、.h*/#include<iostream>#include"Tree.h"using namespace std;#define Stack_Size 100typedef struct /二叉樹結(jié)點(diǎn)類型順序棧 TNode elemStack_Size; int top;TStackvoid InitTStack(&S) /初始化順序棧 S.elem=new charStack_Size; if(!S.elem) Error("Overflow!"); S.top=-1;void Push_T(TStack &S , TNo

20、de T) /壓棧 if( S.top=(Stack_Size-1) ) Error("Stack Overflow!"); S.elem+S.top=T;TNode Pop_T(TStack &S) /出棧 if(S.top=-1) Error("Stack Empty!"); return S.elemtop-;/*String.h*/#include<iostream>using namespace std;typedef struct /動(dòng)態(tài)順序串 char *ch; int len;StringSrting StrNeg(&

21、amp;Str) /求逆序串 String F; for(i=0 ; i<length ; i+) F.chi = Str.chStr.len-1-i; return Fint StrLen(&Str) /求串長(zhǎng) int i; for(i=0 ; Str.chi!='0' ; ) i+; return i;/*Tree.h*/#include<iostream>#include"String.h"#include"CStack.h"#include"TStack.h"using namespa

22、ce std;typedef struct /二叉樹結(jié)點(diǎn) union data /數(shù)據(jù)域 char opr; /運(yùn)算符 int opn; /運(yùn)算數(shù) struct TNode *lchid , *rchild; /指針域TNodetypedef TNode *BiTree; /二叉樹頭結(jié)點(diǎn)int Precedence(char opr) /判斷運(yùn)算符級(jí)別函數(shù)；其中* /的級(jí)別為2，+ -的級(jí)別為1； switch(opr) case'+': case'-': return 1; break; case'*': case'/': re

23、turn 2; break; case'(': case')': case'#': default: return 0; break; bool IsOperator(char opr) /判斷輸入串中的字符是不是合法操作符 if(op='+'|op='-'|op='*'|op='/') return true; else return false;String Convert(String &Str) /將一個(gè)中綴串轉(zhuǎn)換為后綴串 int i; String Output;

24、/輸出串 Output.len=0; CStack S; InitCStack(S); Str.len=StrLen(Str); /求的輸入的串長(zhǎng) for(i=Str.len-1 ; i>=0 ; i-) /對(duì)輸入串逆序掃描 if(Str.chi>=48 && Str.chi<=57) /假如是操作數(shù)，把它添加到輸出串中。 Output.chStr.len-1-i=Str.chi; Output.len+; if( Str.chi=')' ) /假如是右括號(hào)，將它壓棧。 Push_C( S , Str.chi ); while( IsOpera

25、tor( Str.chi ) ) /如果是運(yùn)算符 if( S.top=0 | GetTop(S)=')' | Precedence(Str.chi ) >=Precedence( GetTop(S) ) ) Push_C( S , Str.chi ); break; else Output.chStr.len-1-i=Pop_C(S); Output.len+; if( Str.chi='(' ) /假如是左括號(hào)，棧中運(yùn)算符逐個(gè)出棧并輸出 /直到遇到右括號(hào)。右括號(hào)出棧并丟棄。 while( GetTop(S)!=')' ) Output.c

26、hStr.len-1-i=Pop_C(S); Output.len+; while(S.top!=-1) /假如輸入完畢，棧中剩余的所有操作符出棧并加到輸出串中。 Output.ch+Output.len-1=Pop_C(S); return StrNeg(Output); /輸出Output的逆序即為所求前綴表達(dá)式void CreatBiTree(&T , &Str) /由中綴表達(dá)式生成表達(dá)式二叉樹 String F; TStack S; /用以存放生成的二叉樹結(jié)點(diǎn) InitTStack(S); F=Convert(Str); /求得S的前綴表達(dá)式 for(i=F.len-1

27、 ; i>=0 ; i-) if( !IsOperator(F.chi) ) T=new TNode; T->data=F.chi; T->lchild=NULL; T->rchild=NULL; Push_T(S , T) else T=new TNode; T->data=F.chi; T->lchild=Pop_T( S ); T->rchild=Pop_T( S ); Push_T(S , T); int Calc(int a, char opr, int b) /計(jì)算 switch (opr) case '+': return

28、 a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; int Value(TNode *T) /求表達(dá)式二叉樹的值 if (T->lchild = NULL &&T->rchild = NULL) return T->data; else return Calc( Value(T->lchild) , T->data , Value(T->rchild) );/*JudgeExp.h*/#i

29、nclude<iostream>#include"String.h"#include"Tree.h"using namespace std;bool JudegExp(String Exp) /此函數(shù)驗(yàn)證式子是否正確，即是否符合運(yùn)算規(guī)則。 char check; int error=0; int lb=0; int rb=0; if(StrLen(Exp)=1 && Exp.ch0!='-') return false; else if( (IsOperator(Exp.ch0)&& Exp.c

30、h0!='-' | IsOperator( Exp.chStrLen(Exp)-1 ) ) && Exp.ch0!='(' && Exp.chStrLen(Exp)-1!=')' ) /此處若不加，在遇到某些式子時(shí)，會(huì)出現(xiàn)非法操作。 return false; for(int m=0 ; m<StrLen(Exp) ; m+) check=Exp.chm; if(m=0 && check='-' && (IsDigit(Exp.ch1)!=0 | Exp.ch1

31、='(' ) ) check=Exp.ch+m; if( IsOperand(check) ); /如果是數(shù)字，跳過，不管。 else if(IsOperator(check) if( check=')' ) rb+; if( IsOperator(Exp.chm+1)&&(Exp.chm+1='+'|Exp.chm+1='-'|Exp.chm+1='*'|Exp.chm+1='/'|Exp.chm+1=''|Exp.chm+1=')' ) ) m+; if( Exp.chm=')' ) rb+; else if( IsOperator(Exp.chm+1) ) error+; else if( check='(' ) lb+; if( Exp.chm+1='(' ) m+; lb+; else if(I