重言式判別課程設(shè)計報告

1、合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告20162017學(xué)年第1學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計題目名稱重言式的判別學(xué)生姓名王 芳學(xué)號1404011018專業(yè)班級計算機科學(xué)與技術(shù)14級1班指導(dǎo)教師李紅 何立新2016年9月一、題目【問題描述】一個邏輯表達式如果對于其變元的任一種取值都為真，則稱為重言式；反之，如果對于其變元的任一種取值都為假，則稱為矛盾式；然而，更多的情況下，既非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達式屬于上述哪一類。【基本要求】(1) 邏輯表達式從終端輸入，長度不超過一行。邏輯運算符包括 "|"，"&" 和

2、""，分別表示或、與和非，運算優(yōu)先程度遞增，但可由括號改變，即括號內(nèi)的運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以含有多個空格符。(2) 若是重言式或矛盾式，可以只顯示"True forever"，或"False forever"，否則顯示 "Satisfactible" 以及變量名序列，與用戶交互。若用戶對表達式中變元取定一組值，程序就求出并顯示邏輯表達式的值。 【測試數(shù)據(jù)】(1) (A|A)&(B|B)(2) (A&A)&C(3) A|B|C|D|E|A(4) A&B&a

3、mp;C&B(5) (A|B)&(A|B)(6) A&B|A&B;O ,0;0,1;1,0;1,1 。二、問題分析1、 一個邏輯表達式如果對于其變元的任一種取值均為真，則稱為重言式；反之，如果對于其變元的任一種取值都為假，則稱為矛盾式，若對于其變元的任一種取值既有真，又有假，則稱其為可滿足式。寫一個程序通過真值表判別一個邏輯表達式屬于上述哪一類?；疽笕缦拢?) 邏輯表達式從終端輸入，長度不超過一行。邏輯運算符包括“|”、“&”、“”，分別表示或、與、非，運算優(yōu)先程度遞增，但可有括號改變，即括號內(nèi)的運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以含

4、有多個空格符。2) 若是重言式或矛盾式，可以只顯示“True Forever”或“False Forever”，否則顯示運算中每種賦值和與其相對應(yīng)的表達式的值。2、通過真值表判別邏輯表達式是否為重言式，需解決以下問題：1) 對邏輯表達式中空格符的處理。為了方便對邏輯表達式進行掃描判斷，應(yīng)先去掉表達式中的空格符。2) 算符的優(yōu)先級問題在帶括號的表達式中，界限符包括左右括號以及表達式起始、結(jié)束符“#”。對于一個簡單的表達式求值運算規(guī)則如下：（1）從左至右依次計算。（2）先取反，然后相與，后相或。（3）先括號內(nèi)，后括號外。為統(tǒng)一算法的描述，將運算符和界限符統(tǒng)稱為算符。這樣，算符集為，&，|，

5、（，），#。根據(jù)上述3條規(guī)則，兩個前后相繼出現(xiàn)的算符a1，a2間的優(yōu)先關(guān)系可以歸納如下：（1） 若a1,a2同為“&”或同為“|”，則算符a1的優(yōu)先級大于a2。（2） “”、“&”、“|”的優(yōu)先級依次減小。（3） 由于先括號內(nèi)，后括號外，若a1為“|”、“&”、“”，a2為“（”；或者，a1為“（”，而a2為“|”、“&”、“”，則a1的優(yōu)先級小于a2。（4） 同理，若a1為“|”、“&”、“”，a2為“）”；或者，a1為“）”，而a2為“|”、“&”、“”，則a1的優(yōu)先級大于a2。（5） 若a1、a2同為“（”，則a1的優(yōu)先級小于a2；若a1、

6、a2同為“）”，則a1的優(yōu)先級大于a2。（6） 表達式的起始、結(jié)束符“#”的優(yōu)先級小于其他所有合法出現(xiàn)的算符。（7） 若a1為“（”，a2為“）”；或者，a1、a2同為“#”，則a1、a2優(yōu)先級相同。綜上所述，將兩個相繼出現(xiàn)的算符a1、a2的優(yōu)先關(guān)系進行歸納如表1所示。表1 算符a1和a2間的優(yōu)先關(guān)系a1 a2|&()#|><<<>>&>><<>>>>><>>(<<<<=_)>>>_>>#<<<<

7、;_=我們可以將邏輯表達式的計算類比算術(shù)表達式的計算，通常借助堆棧來實現(xiàn)按運算符的優(yōu)先級完成表達式的求值計算。一個是存放運算符棧，另一個是存放變量或中間結(jié)果棧。 （1） 首先初始化算符棧logic和變量棧，并將表達式的起始符“#”壓入算符棧logic。（2） 依次讀入表達式中的每個字符。若是變量，則為其分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型，并將其壓入變量棧variable；若是運算符，則為其分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型，并與運算符棧logic的棧頂算符進行優(yōu)先級比較，并作如下處理： 若棧頂算符a1的優(yōu)先級低于剛讀入的算符a2，則將

8、a2壓入運算符棧logic。 若棧頂算符a1的優(yōu)先級高于剛讀入的算符a2，則將a1出棧，同時將變量棧variable出棧一次，得到變量A，再判斷棧頂算符a1是否為“”，如果a1不是“”，則繼續(xù)出棧變量棧variable一次，得到變量B，將a1作為根結(jié)點，B作為a1的左孩子，A作為a1的右孩子，并將根結(jié)點a1壓入變量棧variable；如果棧頂算符a1是“”，則將a1作為根結(jié)點，A作為a1的右孩子，a1的左孩子則為空，并將根結(jié)點a1壓入變量棧。 若棧頂算符a1優(yōu)先級與剛讀入的算符a2的優(yōu)先級相同，說明左右括號相遇，或者是表達式的起始、結(jié)束符相遇，只需將棧頂算符（左括號或起始符）出棧即可；當運算符

9、棧logic空時，算法結(jié)束這樣就可以將邏輯表達式構(gòu)造成一棵完整二叉樹，根結(jié)點是優(yōu)先級最小的算符（除了括號和起始結(jié)束符，在構(gòu)造二叉樹的過程中已被脫去）。如(A|A)&(B|B)構(gòu)造成的二叉樹如圖1所示圖1 表達式構(gòu)造的二叉樹 1) 變量的賦值問題若只有1個變量，則有21種情況的賦值；若有2個變量，易知有22種情況的賦值；若有3各變量，則有23種情況的賦值，那么如果有n個變量，就有2n種情況的賦值。既然要對變量進行賦值，首先要找到邏輯表達式中的變量，并確定變量的個數(shù)。 2) 邏輯表達式取值的判斷 由上述對運算符的優(yōu)先級的分析可知，對邏輯表達式的計算，就是中序遍歷由優(yōu)先級確定的邏輯表達式構(gòu)成

10、的二叉樹。5）重言式的判別可以將給變量的所有賦值的邏輯表達式的邏輯值相加，如果相加結(jié)果與2n相等，則為重言式；若相加結(jié)果為0，則為矛盾式；否則為可滿足式。本問題的關(guān)鍵和難點在于算符優(yōu)先級的判斷和二叉樹的構(gòu)造。三、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計1、數(shù)據(jù)結(jié)構(gòu)的選擇通過問題分析可知，需要用到的數(shù)據(jù)結(jié)構(gòu)有堆棧和二叉樹。1) 對于堆棧選用順序棧結(jié)構(gòu)來進行存放算符或變量，存放的都是二叉樹的結(jié)點。設(shè)有兩個堆棧，一個是存放運算符棧，另一個是存放變量或中間結(jié)果棧。2) 對于二叉樹，選用二叉樹的鏈接存儲結(jié)構(gòu)，其結(jié)點存放得都是表達式中的元素。將表達式構(gòu)造成一棵二叉樹。2、概要設(shè)計從整體上可以分為三個模塊：第一個模塊：屬于

11、堆棧和二叉樹結(jié)點類型的定義typedef struct stack /識別表達式使用的堆棧定義,它存放的都是樹的結(jié)構(gòu) /棧中的元素都是樹的結(jié)點結(jié)構(gòu)bitree *base; /棧底指針bitree *top; /棧頂指針int stacksize; /棧容量seqstack;typedef struct node /根據(jù)表達式建立的二叉樹的結(jié)點定義char data;struct node *lchild; struct node *rchild;BiTNode,*bitree;第二個模塊：主要函數(shù)及其功能。 堆棧的創(chuàng)建void creatstack(sqstack &st)；初始化棧

12、void setstack(seqstack &st)；進棧void push(sqstack &st,bitree e)；出棧void pop(sqstack &st,bitree &e)；將邏輯表達式中的元素轉(zhuǎn)換為二叉樹結(jié)點的形式，使棧中存儲的都是二叉樹的結(jié)點。void creattree(char s,bitree &tree)；通過優(yōu)先級將邏輯表達式構(gòu)造成一顆完整的二叉樹void create(bitree &zigen,bitree l,bitree r)；對邏輯表達式求值int valuetree(bitree tree)；生成變量的

13、各種取值組合void creatzuhe(int n,int m,char a)；邏輯運算符的優(yōu)先級判別，返回值為“<”、“>”、“=”char youxianji(char m,char n)；第四個模塊為于用戶的交互void user()；流程圖： 圖2 程序流程圖開始mainmeun輸入表達式1. 計算機2. 用戶3. 3.返回建樹建樹計算機窮舉用戶輸入變量值輸出結(jié)果繼續(xù)結(jié)束213NY四、算法思想1、窮舉法思想通過真值表來判斷重言式，需要一一給變量賦值，共有2n中情況（n表示變量的個數(shù)），這里用到窮舉的思想。2、遞歸與分治思想每給變量賦一組值，通過遞歸中序遍歷二叉樹求值，這里

14、用到了遞歸與分治思想。3、運算符的優(yōu)先級判斷思想（見問題分析算符的優(yōu)先級問題分析第5頁）五、詳細設(shè)計和主要編碼段首先將用戶輸入的邏輯表達式存到char *str當中，然后去除邏輯表達式中的空格符。for(;*pstr!=NULL;pstr+,n+)if(strn!=' ') strii+=*pstr; /去除表達式中的空格 此時stri當中存儲的就是沒有空格符的邏輯表達式。通過問題分析，需找到表達式中的變量，并確定變量的個數(shù)。下面的代碼就是實現(xiàn)此功能。for(int k=0;k< strlen(stri);k+) if(strik>=65&&stri

15、k<=90)/找到變量 int mark=0; /標記變量for(int j=0;j<m;j+)if(blj=strik)/將找到的變量與bl中已找到過的變量比較，若相等則將變量標記置為1，表示找到的變量在前面已出現(xiàn)過mark=1;break;if(mark=0)/若標記為0，表示找到的變量沒有重復(fù)，并將其記錄到bl中，變量個數(shù)m加1。 blm=strk;m+;/m是變量個數(shù) 此時bl當中存儲的就是變量，m就是變量個數(shù)，那么變量賦值的情況就有2m種。下面對生成變量的各種取值組合的算法進行分析和說明。int zuhe30用來存儲變量的取值組合，為了方便說明，采用兩個變量進行算法敘述。

16、AB第n次數(shù)000011102113 表2 變量賦值實例 從表2可以發(fā)現(xiàn)給變量賦值的次數(shù)n與變量的取值組合成的二進制數(shù)相等，能得到一個規(guī)律：變量的取值組合zuhe二進制數(shù)（從低位到高位）的第i位數(shù)取值等于(n>>i)%2。用一下代碼可以實現(xiàn)第n次對變量的賦值組合int lzp=m;for(int i=0;i<m;i+)zuhebllzp-65=(n>>i)%2;lzp-;下面說明優(yōu)先級的判斷。char bijiao77用來存放算符間的優(yōu)先關(guān)系表中的數(shù)據(jù)。int i,j; bijiao77=' ','|','&'

17、;,'','(',')','#', /二維數(shù)組比較優(yōu)先級先后'|','>','<','<','<','>','>','&','>','>','<','<','>','>', '','>',

18、9;>','>','<','>','>','(','<','<','<','<','=',' ',')','>','>','>',' ','>','>','#','<','&

19、lt;','<','<',' ','='for(i=0;i<7;i+)if(bijiao0i=a2) /找到a2運算符的列號break;for(j=0;j<7;j+) /找到a1運算符的行號if(bijiaoj0=a1) break;return bijiaoji; /返回優(yōu)先級的符號:>、<、=下面說明將表達式構(gòu)成二叉樹的過程。s=stri是邏輯表達式的首地址。while(*s!=NULL) /循環(huán)條件，為空則掃描結(jié)束 if(int(*s)>=65&&int(*s

20、)<=90) /讀取的是變量 variables=(bitree)malloc(sizeof(node);/分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型 variables->data=*s; push(variable,variables); /入變量棧else if(int(*s)>90|int(*s)<65) /讀取的邏輯運算符 gettop(logic,e); /取運算符棧的棧頂元素進行優(yōu)先級比較 switch(youxianji(*s,e->data) case '<': /棧頂?shù)倪\算符優(yōu)先級低,邏輯運算符進棧l

21、ogics=(bitree)malloc(sizeof(node);/分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型logics->data=*s;push(logic,logics);break; case '=': pop(logic,kuohao); /括號并接受下一個字符break; case '>': /棧頂?shù)倪\算符優(yōu)先級高,變量出棧運算pop(logic,g); /彈出邏輯運算符gpop(variable,a); /彈出變量ab=NULL; /''只有右子樹if(g->data!=''

22、;) pop(variable,b); /出棧變量bcreate(g,b,a); /將變量b作為g的左子樹，a作為g的右子樹，若a是變量，將其左、右孩子置空，若b是變量，將其左、右孩子置空push(variable,g);/將臨時的根g作為新的變量壓入變量棧中g(shù)ettop(logic,e);/取變量棧棧頂算符eif(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>') /如果讀入算符*s不是結(jié)束符也不是右括號，并且棧頂算符優(yōu)先級小于讀入算符優(yōu)先級將讀入的算符入棧lo

23、gics=(bitree)malloc(sizeof(node);/分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型 logics->data=*s; push(logic,logics); /邏輯運算符入棧 else s=s-1;/若棧頂算符優(yōu)先級大于讀入算符優(yōu)先級或讀入算符為“#”或“）” break;s+;tree=g;下面說明對邏輯表達式的求值過程。中序遍歷二叉樹int valuetree(bitree tree) /根據(jù)變量的取值組合并利用邏輯表達式的性質(zhì)對樹進行求值 if(!tree) return 0; /遇到空的結(jié)點 else if(tree->da

24、ta!='|'&&tree->data!='&'&&tree->data!='') /找到的是變量return zuheint(tree->data)-65; /返回對應(yīng)變量賦予的值（0或1） else if(int(tree->data)<65|int(tree->data)>90) /找到的是運算符switch(tree->data) case '|': return(valuetree(tree->lchild)|valuetree

25、(tree->rchild); /遞歸調(diào)用 break; case '&': return(valuetree(tree->lchild)&&valuetree(tree->rchild); /遞歸調(diào)用 break; case '': return(!valuetree(tree->rchild); /遞歸調(diào)用 break; default: return 0;else return 0;最后說明判斷邏輯表達式或為重言式，或為矛盾式或為可滿足式。每給變量一組值，調(diào)用一次int valuetree(bitree tr

26、ee)函數(shù)求其邏輯值，需要給變量2n組值，則需求其邏輯值2n次，把每次求得的邏輯值相加，得到數(shù)字SUM，若SUM=2n,則邏輯表達式為重言式；若SUM=0，則邏輯表達式為矛盾式；若0<SUM<2n,則邏輯表達式為可滿足式。若表達式為可滿足式，則輸出運算中每種賦值和與其相對應(yīng)的表達式的值。六、上機調(diào)試情況記錄出現(xiàn)的問題及解決方法問題：a) 測試題目給定的數(shù)據(jù)A&B|A&B，發(fā)現(xiàn)其結(jié)果不正確，原因是沒有正確的解決優(yōu)先級，建樹的過程中，運算符入棧時，如果檢測到的表達式中的算符優(yōu)先級低于棧頂?shù)膬?yōu)先級，則應(yīng)出棧運算符，在出棧運算符后，如果檢測到的表達式中的算符（并且算符不是結(jié)

27、束符#也不是）的優(yōu)先級依舊低于棧頂算符,應(yīng)該繼續(xù)算符出棧，而不是算符入棧。解決方法：將算符入棧條件if(*s!='#'&&*s!=')')改為if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>')b) 測試數(shù)據(jù)時如果邏輯表達式的變量不是遞增按順序輸入（如：A&B&F&G），結(jié)果會出錯。原因是在給變量組合賦值時，賦值組合數(shù)組的小標是遞增順序的，而在遞歸調(diào)用求值函數(shù)時用到的變量組合值數(shù)組的下標卻

28、是與變量的ACS編碼有關(guān)的，兩者對不上。解決方法：在生成變量組合數(shù)時，將zuhei=(n>>i)%2改為zuhealzp-65=(n>>i)%2;七、測試用例、結(jié)果及其算法性能分析（一）、初始界面（二）、測試用例及結(jié)果(1) (A|A)&(B|B)（重言式）(2) (A&A)&C（矛盾式）(3) A|B|C|D|E|A（重言式）(4) A&B&C&B（矛盾式）(5) (A|B)&(A|B)（可滿足式）(6) A&B|A&B;O ,0;0,1;1,0;1,1 。（可滿足式） 通過測試驗證結(jié)果都正確，實

29、現(xiàn)了題目的要求。（三）、算法性能分析1、算法的時間性能分析用窮舉法列真值表有2n（n為變量個數(shù)）種情況，為每一種情況的所有變量賦值的次數(shù)為n,則為所有情況的變量賦值次數(shù)為n*2n次，即在函數(shù)void creatzuhe(int n,int m,char a)中的語句需執(zhí)行n*2n次，是整個算法當中頻度最大的語句，由于算法的時間復(fù)雜度考慮的只是對于問題規(guī)模n的增長率，所以該算法的時間復(fù)雜度為T(n)=O(n*2n)。2、算法的空間性能分析本算法的空間復(fù)雜度較低，需要一個zuhe30的數(shù)組來存放變量的取值，一個大小為M的數(shù)組存放邏輯表達式，一個M的二叉樹鏈接存放邏輯表達式構(gòu)成的樹結(jié)點。兩個堆棧長度

30、不超過M，所以空間復(fù)雜度為O（M）。（四）、經(jīng)驗和體會初拿到本問題，就覺得與學(xué)過的帶括號的算術(shù)表達式計算問題相似。其最關(guān)鍵的是算符優(yōu)先級的判斷，可以將它類比算術(shù)表達式列出同數(shù)據(jù)結(jié)構(gòu)與算法課本上表4-1類似的算符的優(yōu)先關(guān)系表表1。通過查表來判斷算符的優(yōu)先級就變得簡易了。觀察邏輯表達式可以發(fā)現(xiàn)，對邏輯表達式的計算類似于對二叉樹的中序遍歷，可以將邏輯表達式通過優(yōu)先級將其構(gòu)造成一棵二叉樹。當然最終實現(xiàn)過程中有很多細節(jié)問題需要注意，通過一步步測試、調(diào)試程序找到問題，并改善，知道最終解決問題。八、用戶使用說明1、運行程序進入顯示文本方式的用戶界面；2、根據(jù)提示輸入要判別的邏輯表達式（表達式中可以有空格）3

31、、輸入表達式后出現(xiàn)菜單選項，用戶可以選擇程序自動窮舉賦值法和用戶賦值法進行判別；4、在顯示相應(yīng)結(jié)果后，根據(jù)提示信息在進行下一步。九、參考文獻1 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版社，2006年5月。2 嚴蔚敏，吳偉明. 數(shù)據(jù)結(jié)構(gòu). 北京：清華大學(xué)出版社，2007年5月。3 李春葆. 數(shù)據(jù)結(jié)構(gòu)教程. 北京：清華大學(xué)出版社，2003年5月。4蹇強，羅宇. 數(shù)據(jù)結(jié)構(gòu). 北京：郵電大學(xué)出版社，2004年5月。5 金遠平. 數(shù)據(jù)結(jié)構(gòu)（C+描述. 北京：清華大學(xué)出版社 2005年5月。十、附錄（完整代碼）#include "stdlib.h" /調(diào)用stdlib.h

32、里面的函數(shù)#include "stdio.h"#include "iostream.h" #include "string.h"/包含字符串處理函數(shù)的頭文件#include "math.h"/調(diào)用數(shù)學(xué)函數(shù)庫#include "iomanip.h"/是I/O流控制頭文件#define maxsize 100int zuhemaxsize; /變量的取值組合數(shù)組定義int N; /變量個數(shù)typedef struct node /根據(jù)表達式建立的二叉樹的結(jié)點定義char data;struct no

33、de *lchild; struct node *rchild;BiTNode,*bitree;typedef struct stack /識別表達式使用的堆棧定義,它存放的都是樹的結(jié)構(gòu) /棧中的元素都是樹的結(jié)點結(jié)構(gòu)bitree *base; /棧底指針bitree *top; /棧頂指針int stacksize; /棧容量seqstack;void creatzuhe(int n,int m,char a)/生成變量的組合數(shù) int lzp=m-1;for(int i=0;i<m;i+)zuhealzp-65=(n>>i)%2;lzp-;void create(bitre

34、e &f,bitree l,bitree r) /自底向上地根據(jù)運算符地優(yōu)先級來建立分子樹函數(shù) f->lchild=l; /分樹的鏈接 f->rchild=r; /分樹的鏈接 if(l&&r)if(int(l->data)>=65&&int(l->data)<=90) /左子樹l->lchild=NULL;l->rchild=NULL;if(int(r->data)>=65&&int(r->data)<=90) /右子樹r->lchild=NULL;r->

35、rchild=NULL;char youxianji(char m,char n) /邏輯運算符的優(yōu)先級判別int i,j;char bijiao77=' ','|','&','','(',')','#', /二維數(shù)組比較優(yōu)先級先后'|','>','<','<','<','>','>','&','&

36、gt;','>','<','<','>','>', '','>','>','>','<','>','>','(','<','<','<','<','=',' ',')','&

37、gt;','>','>',' ','>','>','#','<','<','<','<',' ','='for(i=0;i<7;i+)if(bijiao0i=m) /找到m運算符的列號break;for(j=0;j<7;j+) /找到n運算符的行號if(bijiaoj0=n) break;return bijiaoji; /返回優(yōu)先級的符

38、號:>、<、=void setstack(seqstack &st) /初始化棧st.base=(bitree *)malloc(maxsize*sizeof(node);st.top=st.base; st.stacksize=maxsize; /棧容量void push(seqstack &st,bitree e) /入棧if(st.top-st.base<st.stacksize) /符合條件入棧*st.top=e;st.top+; else cout<<"ERROR!"<<endl; /不符合輸出ERROR!

39、void pop(seqstack &st,bitree &e) /出棧if(st.top=st.base) cout<<"ERROR!"<<endl; /不符合條件輸出ERROR! st.top-; /符合條件 e=*st.top;void gettop(seqstack &st,bitree &e) /取棧頂元素if(st.top=st.base) cout<<"ERROR!"<<endl/不符合條件輸出ERROR! e=*(st.top-1); /符合取棧頂元素void

40、 creattree(char s,bitree &tree) /根據(jù)邏輯表達式將數(shù)據(jù)存入二叉樹中，定義兩個棧 seqstack variable; /變量棧 seqstack logic; /邏輯運算符棧 setstack(variable); /變量棧初始化 setstack(logic); /邏輯運算符棧初始化 bitree logic1,variables,logics,e,a,b,g,kuohao;/定義棧中的元素,g為最后的二叉樹的根 logic1=(bitree)malloc(sizeof(node);/分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型 l

41、ogic1->data='#' /將邏輯運算符棧的棧底元素設(shè)為'#' push(logic,logic1); /將邏輯運算符棧入棧. while(*s!=NULL) if(int(*s)>=65&&int(*s)<=90) /讀取的是變量 variables=(bitree)malloc(sizeof(node);/分配結(jié)構(gòu)node的size大小的內(nèi)存,強制轉(zhuǎn)換為bitree類型 variables->data=*s; push(variable,variables); /入變量棧else if(int(*s)>90

42、|int(*s)<65) /讀取的邏輯運算符 gettop(logic,e); /取運算符棧的棧頂元素進行優(yōu)先級比較 switch(youxianji(*s,e->data) case '<': /棧頂?shù)倪\算符優(yōu)先級低,邏輯運算符進棧logics=(bitree)malloc(sizeof(node);/強制轉(zhuǎn)換為bitree類型logics->data=*s;push(logic,logics);break; case '=': pop(logic,kuohao); /括號并接受下一個字符break; case '>

43、9;: /棧頂?shù)倪\算符優(yōu)先級高,變量出棧運算pop(logic,g); /彈出邏輯運算符pop(variable,a); /彈出變量b=NULL; /''只有右子樹if(g->data!='') pop(variable,b); create(g,b,a); /建樹的函數(shù)調(diào)用 push(variable,g);/將臨時的根作為新的變量壓入變量棧中g(shù)ettop(logic,e);if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>

44、9;) logics=(bitree)malloc(sizeof(node);/強制轉(zhuǎn)換為bitree類型 logics->data=*s; push(logic,logics); /邏輯運算符入棧else s=s-1;break;s+;tree=g; int valuetree(bitree tree) /根據(jù)變量的取值組合并利用邏輯表達式的性質(zhì)對樹進行求值 if(!tree) return 0; /遇到空的結(jié)點 else if(tree->data!='|'&&tree->data!='&'&&tre

45、e->data!='') /找到的是變量return zuheint(tree->data)-65; /返回值 else if(int(tree->data)<65|int(tree->data)>90) /找到的是運算符switch(tree->data) case '|': return(valuetree(tree->lchild)|valuetree(tree->rchild); break; case '&': return(valuetree(tree->lchild

46、)&&valuetree(tree->rchild); break; case '': return(!valuetree(tree->rchild); break; default: return 0;else return 0;void user(int m,char b) /用戶輸入變量的一組取值情況 int i; cout<<"請依次輸入你的變量取值(0或1)"<<endl; for(i=0;i<m;i+) cout<<bi<<" " /轉(zhuǎn)化為cha

47、r類型輸出 cout<<endl;for(i=0;i<m;i+) cin>>zuhebi-65;void print()cout<<""<<endl; cout<<" "<<endl; cout<<" 你好！ "<<endl; cout<<" 歡迎使用重言式判別軟件！ "<<endl; cout<<" "<<endl; cout<<&q

48、uot;"<<endl;void meun() /菜單函數(shù)system("cls"); /清屏函數(shù)print();char strmaxsize,strimaxsize,*pstr,q,bl20;int j,i=0,choose=1,sum,n=0,m=0;bitree Tree;int SUM=0; /用于累加變量的每種組合的邏輯表達式的結(jié)果;cout<<"請輸入邏輯表達式的表達式:例如(A|B&C) "<<endl;scanf("%n",str); /讀取包含多個空格的邏輯表達

49、式pstr=str;for(;*pstr!=NULL;pstr+,n+) /邏輯表達式的正確讀取,if(strn>=97&&strn<=122) strn=strn-32;/將小寫轉(zhuǎn)換成大寫if(strn!=' ') strii+=*pstr; /去除表達式中的空格 int nu=strlen(stri);for(int k=0;k<nu;k+) if(strik>=65&&strik<=90) int mark=0; /標記變量for(int j=0;j<m;j+)if(blj=strik)mark=1;br

50、eak;if(mark=0)blm=strk;m+;/m是變量個數(shù) sum=int(pow(2,m); strii='#' /最后一字符后加入'#',與運算符棧的棧底元素'#'對應(yīng)strii+1='0' /結(jié)束標志'0'cout<<"請選擇你要的操作"<<endl; cout<<" "<<endl; cout<<" "<<endl; cout<<" "&

51、lt;<endl; cout<<" "<<endl;cout<<" 1 計算機窮舉法 "<<endl;cout<<" 2 用戶自定義給變量賦值 "<<endl;cout<<" 3 重新開始 "<<endl;cout<<" 0 退出 "<<endl;cout<<"請選擇你要的操作: " /提示信息cin>>choose;while

52、(choose!=1&&choose!=2&&choose!=3&&choose!=0)cout<<"您輸入的有誤,請您重新輸入:" /提示信息cin>>choose;switch(choose)case 1:/判別重言式的類別creattree(stri,Tree); /建立重言式的二叉樹 for(j=0;j<sum;j+) creatzuhe(j,m,bl); /產(chǎn)生變量取值組合SUM+=valuetree(Tree); /SUM累加 strii='0' /加入結(jié)束標志以便輸出邏輯表達式 if(SUM=0) /矛盾式cout<<"邏輯表達式:"<<stri<<endl;cout<<"False forever"<<endl;if(SUM=sum) /重言式