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

合肥學院計算機科學與技術(shù)系課程設(shè)計報告～第1學期課程數(shù)據(jù)構(gòu)造與算法課程設(shè)計題目名稱重言式鑒別學生姓名王芳學號專業(yè)班級計算機科學與技術(shù)14級1班指引教師李紅何立新9月一、題目【問題描述】一種邏輯表達式如果對于其變元任一種取值都為真，則稱為重言式；反之，如果對于其變元任一種取值都為假，則稱為矛盾式；然而，更多狀況下，既非重言式，也非矛盾式。試寫一種程序，通過真值表鑒別一種邏輯表達式屬于上述哪一類?！净疽?guī)定】(1)邏輯表達式從終端輸入，長度不超過一行。邏輯運算符涉及"|"，"&"和"~"，分別表達或、與和非，運算優(yōu)先限度遞增，但可由括號變化，即括號內(nèi)運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以具有各種空格符。(2)若是重言式或矛盾式，可以只顯示"Trueforever"，或"Falseforever"，否則顯示"Satisfactible"以及變量名序列，與顧客交互。若顧客對表達式中變元取定一組值，程序就求出并顯示邏輯表達式值?！緶y試數(shù)據(jù)】(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。二、問題分析1、一種邏輯表達式如果對于其變元任一種取值均為真，則稱為重言式；反之，如果對于其變元任一種取值都為假，則稱為矛盾式，若對于其變元任一種取值既有真，又有假，則稱其為可滿足式。寫一種程序通過真值表鑒別一種邏輯表達式屬于上述哪一類?；疽?guī)定如下：邏輯表達式從終端輸入，長度不超過一行。邏輯運算符涉及“|”、“&”、“~”，分別表達或、與、非，運算優(yōu)先限度遞增，但可有括號變化，即括號內(nèi)運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以具有各種空格符。若是重言式或矛盾式，可以只顯示“TrueForever”或“FalseForever”，否則顯示運算中每種賦值和與其相相應(yīng)表達式值。2、通過真值表鑒別邏輯表達式與否為重言式，需解決如下問題：對邏輯表達式中空格符解決。為了以便對邏輯表達式進行掃描判斷，應(yīng)先去掉表達式中空格符。算符優(yōu)先級問題在帶括號表達式中，界限符涉及左右括號以及表達式起始、結(jié)束符“#”。對于一種簡樸表達式求值運算規(guī)則如下：（1）從左至右依次計算。（2）先取反，然后相與，后相或。（3）先括號內(nèi)，后括號外。為統(tǒng)一算法描述，將運算符和界限符統(tǒng)稱為算符。這樣，算符集為{~，&，|，（，），#}。依照上述3條規(guī)則，兩個先后相繼浮現(xiàn)算符a1，a2間優(yōu)先關(guān)系可以歸納如下：若a1,a2同為“&”或同為“|”，則算符a1優(yōu)先級不不大于a2?！皛”、“&”、“|”優(yōu)先級依次減小。由于先括號內(nèi)，后括號外，若a1為“|”、“&”、“~”，a2為“（”；或者，a1為“（”，而a2為“|”、“&”、“~”，則a1優(yōu)先級不大于a2。同理，若a1為“|”、“&”、“~”，a2為“）”；或者，a1為“）”，而a2為“|”、“&”、“~”，則a1優(yōu)先級不不大于a2。若a1、a2同為“（”，則a1優(yōu)先級不大于a2；若a1、a2同為“）”，則a1優(yōu)先級不不大于a2。表達式起始、結(jié)束符“#”優(yōu)先級不大于其她所有合法浮現(xiàn)算符。若a1為“（”，a2為“）”；或者，a1、a2同為“#”，則a1、a2優(yōu)先級相似。綜上所述，將兩個相繼浮現(xiàn)算符a1、a2優(yōu)先關(guān)系進行歸納如表1所示。表1算符a1和a2間優(yōu)先關(guān)系a1a2|&~()#|><<<>>&>><<>>~>>><>>(<<<<=___)>>>___>>#<<<<___=咱們可以將邏輯表達式計算類比算術(shù)表達式計算，普通借助堆棧來實現(xiàn)按運算符優(yōu)先級完畢表達式求值計算。一種是存儲運算符棧，另一種是存儲變量或中間成果棧。一方面初始化算符棧logic和變量棧，并將表達式起始符“#”壓入算符棧logic。依次讀入表達式中每個字符。若是變量，則為其分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型，并將其壓入變量棧variable；若是運算符，則為其分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型，并與運算符棧logic棧頂算符進行優(yōu)先級比較，并作如下解決：若棧頂算符a1優(yōu)先級低于剛讀入算符a2，則將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é)束符相遇，只需將棧頂算符（左括號或起始符）出棧即可；當運算符棧logic空時，算法結(jié)束這樣就可以將邏輯表達式構(gòu)導致一棵完整二叉樹，根結(jié)點是優(yōu)先級最小算符（除了括號和起始結(jié)束符，在構(gòu)造二叉樹過程中已被脫去）。如(A|~A)&(B|~B)構(gòu)導致二叉樹如圖1所示圖1表達式構(gòu)造二叉樹變量賦值問題若只有1個變量，則有21種狀況賦值；若有2個變量，易知有22種狀況賦值；若有3各變量，則有23種狀況賦值，那么如果有n個變量，就有2n種狀況賦值。既然要對變量進行賦值，一方面要找到邏輯表達式中變量，并擬定變量個數(shù)。邏輯表達式取值判斷由上述對運算符優(yōu)先級分析可知，對邏輯表達式計算，就是中序遍歷由優(yōu)先級擬定邏輯表達式構(gòu)成二叉樹。5）重言式鑒別可以將給變量所有賦值邏輯表達式邏輯值相加，如果相加成果與2n相等，則為重言式；若相加成果為0，則為矛盾式；否則為可滿足式。本問題核心和難點在于算符優(yōu)先級判斷和二叉樹構(gòu)造。三、數(shù)據(jù)構(gòu)造選取和概要設(shè)計1、數(shù)據(jù)構(gòu)造選取通過問題分析可知，需要用到數(shù)據(jù)構(gòu)造有堆棧和二叉樹。對于堆棧選用順序棧構(gòu)造來進行存儲算符或變量，存儲都是二叉樹結(jié)點。設(shè)有兩個堆棧，一種是存儲運算符棧，另一種是存儲變量或中間成果棧。對于二叉樹，選用二叉樹鏈接存儲構(gòu)造，其結(jié)點存儲得都是表達式中元素。將表達式構(gòu)導致一棵二叉樹。2、概要設(shè)計從整體上可以分為三個模塊：第一種模塊：屬于堆棧和二叉樹結(jié)點類型定義typedefstructstack//辨認表達式使用堆棧定義,它存儲都是樹構(gòu)造{//棧中元素都是樹結(jié)點構(gòu)造 bitree*base；//棧底指針 bitree*top；//棧頂指針 intstacksize；//棧容量}seqstack;typedefstructnode//依照表達式建立二叉樹結(jié)點定義{ chardata; structnode*lchild； structnode*rchild;}BiTNode,*bitree;第二個模塊：重要函數(shù)及其功能。堆棧創(chuàng)立voidcreatstack(sqstack&st){}；初始化棧voidsetstack(seqstack&st){}；進棧voidpush(sqstack&st,bitreee){}；出棧voidpop(sqstack&st,bitree&e){}；將邏輯表達式中元素轉(zhuǎn)換為二叉樹結(jié)點形式，使棧中存儲都是二叉樹結(jié)點。voidcreattree(chars[],bitree&tree){}；通過優(yōu)先級將邏輯表達式構(gòu)導致一顆完整二叉樹voidcreate(bitree&zigen,bitreel,bitreer){}；對邏輯表達式求值intvaluetree(bitreetree){}；生成變量各種取值組合voidcreatzuhe(intn,intm,chara[]){}；邏輯運算符優(yōu)先級鑒別，返回值為“<”、“>”、“=”charyouxianji(charm,charn){}；第四個模塊為于顧客交互voiduser(){}；流程圖：圖2程序流程圖開始開始mainmeun輸入表達式計算機顧客3.返回建樹建樹計算機窮舉顧客輸入變量值輸出成果繼續(xù)結(jié)束213NY四、算法思想1、窮舉法思想通過真值表來判斷重言式，需要一一給變量賦值，共有2^n中狀況（n表達變量個數(shù)），這里用到窮舉思想。2、遞歸與分治思想每給變量賦一組值，通過遞歸中序遍歷二叉樹求值，這里用到了遞歸與分治思想。3、運算符優(yōu)先級判斷思想（見問題分析算符優(yōu)先級問題分析第5頁）五、詳細設(shè)計和重要編碼段一方面將顧客輸入邏輯表達式存到char*str當中，然后去除邏輯表達式中空格符。for(;*pstr!=NULL;pstr++,n++){ if(str[n]!='')stri[i++]=*pstr；//去除表達式中空格 }此時stri當中存儲就是沒有空格符邏輯表達式。通過問題分析，需找到表達式中變量，并擬定變量個數(shù)。下面代碼就是實現(xiàn)此功能。 for(intk=0;k<strlen(stri);k++) if(stri[k]>=65&&stri[k]<=90)//找到變量 { intmark=0；//標記變量 for(intj=0;j<m;j++) { if(bl[j]==stri[k])//將找到變量與bl[]中已找到過變量比較，若相等則將變量標記置為1，表達找到變量在前面已浮現(xiàn)過 { mark=1;break; } } if(mark==0)//若標記為0，表達找到變量沒有重復，并將其記錄到bl[]中，變量個數(shù)m加1。 { bl[m]=str[k]; m++;//m是變量個數(shù) } }此時bl[]當中存儲就是變量，m就是變量個數(shù)，那么變量賦值狀況就有2m種。下面對生成變量各種取值組合算法進行分析和闡明。intzuhe[30]用來存儲變量取值組合，為了以便闡明，采用兩個變量進行算法論述。AB第n次數(shù)000011102113表2變量賦值實例從表2可以發(fā)現(xiàn)給變量賦值次數(shù)n與變量取值組合成二進制數(shù)相等，能得到一種規(guī)律：變量取值組合zuhe[]二進制數(shù)（從低位到高位）第i位數(shù)取值等于(n>>i)%2。用一下代碼可以實現(xiàn)第n次對變量賦值組合intlzp=m;for(inti=0;i<m;i++){ zuhe[bl[lzp]-65]=(n>>i)%2; lzp--;}下面闡明優(yōu)先級判斷。charbijiao[7][7]用來存儲算符間優(yōu)先關(guān)系表中數(shù)據(jù)。inti,j; bijiao[7][7]={ '','|','&','~','(',')','#'，//二維數(shù)組比較優(yōu)先級先后 '|','>','<','<','<','>','>', '&','>','>','<','<','>','>'， '~','>','>','>','<','>','>', '(','<','<','<','<','=','', ')','>','>','>','','>','>', '#','<','<','<','<','','='}; for(i=0;i<7;i++) if(bijiao[0][i]==a2)//找到a2運算符列號 break; for(j=0;j<7;j++)//找到a1運算符行號 if(bijiao[j][0]==a1) break; returnbijiao[j][i]；//返回優(yōu)先級符號:>、<、=下面闡明將表達式構(gòu)成二叉樹過程。s=stri是邏輯表達式首地址。while(*s!=NULL)//循環(huán)條件，為空則掃描結(jié)束{ if(int(*s)>=65&&int(*s)<=90)//讀取是變量 { variables=(bitree)malloc(sizeof(node)); //分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型variables->data=*s;push(variable,variables)；//入變量棧 } elseif(int(*s)>90||int(*s)<65)//讀取邏輯運算符 {gettop(logic,e)；//取運算符棧棧頂元素進行優(yōu)先級比較switch(youxianji(*s,e->data)) {case'<'：//棧頂運算符優(yōu)先級低,邏輯運算符進棧 logics=(bitree)malloc(sizeof(node)); //分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型 logics->data=*s; push(logic,logics); break;case'='： pop(logic,kuohao)；//括號并接受下一種字符 break;case'>'：//棧頂運算符優(yōu)先級高,變量出棧運算 pop(logic,g)；//彈出邏輯運算符g pop(variable,a)；//彈出變量a b=NULL；//'~'只有右子樹 if(g->data!='~') pop(variable,b)；//出棧變量b create(g,b,a)；//將變量b作為g左子樹，a作為g右子樹，若a是變量，將其左、右孩子置空，若b是變量，將其左、右孩子置空 push(variable,g);//將暫時根g作為新變量壓入變量棧中 gettop(logic,e);//取變量棧棧頂算符e if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>')//如果讀入算符*s不是結(jié)束符也不是右括號，并且棧頂算符優(yōu)先級不大于讀入算符優(yōu)先級將讀入算符入棧 { logics=(bitree)malloc(sizeof(node));//分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型 logics->data=*s; push(logic,logics)；//邏輯運算符入棧 } elses=s-1;//若棧頂算符優(yōu)先級不不大于讀入算符優(yōu)先級或讀入算符為“#”或“）” break; } } s++; } tree=g;}下面闡明對邏輯表達式求值過程。中序遍歷二叉樹intvaluetree(bitreetree)//依照變量取值組合并運用邏輯表達式性質(zhì)對樹進行求值{if(!tree)return0；//遇到空結(jié)點elseif(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//找到是變量 returnzuhe[int(tree->data)-65]；//返回相應(yīng)變量賦予值（0或1）elseif(int(tree->data)<65||int(tree->data)>90)//找到是運算符 switch(tree->data) {case'|'： return(valuetree(tree->lchild)||valuetree(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：return0; } elsereturn0;}最后闡明判斷邏輯表達式或為重言式，或為矛盾式或為可滿足式。每給變量一組值，調(diào)用一次intvaluetree(bitreetree)函數(shù)求其邏輯值，需要給變量2n組值，則需求其邏輯值2n次，把每次求得邏輯值相加，得到數(shù)字SUM，若SUM=2n,則邏輯表達式為重言式；若SUM=0，則邏輯表達式為矛盾式；若0<SUM<2n,則邏輯表達式為可滿足式。若表達式為可滿足式，則輸出運算中每種賦值和與其相相應(yīng)表達式值。六、上機調(diào)試狀況記錄浮現(xiàn)問題及解決辦法問題：測試題目給定數(shù)據(jù)A&~B|~A&B，發(fā)現(xiàn)其成果不對的，因素是沒有對的解決優(yōu)先級，建樹過程中，運算符入棧時，如果檢測到表達式中算符優(yōu)先級低于棧頂優(yōu)先級，則應(yīng)出棧運算符，在出棧運算符后，如果檢測到表達式中算符（并且算符不是結(jié)束符’#’也不是’）’）優(yōu)先級仍舊低于棧頂算符,應(yīng)當繼續(xù)算符出棧，而不是算符入棧。解決辦法：將算符入棧條件if(*s!='#'&&*s!=')')改為if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>')測試數(shù)據(jù)時如果邏輯表達式變量不是遞增按順序輸入（如：A&B&F&G），成果會出錯。因素是在給變量組合賦值時，賦值組合數(shù)組小標是遞增順序，而在遞歸調(diào)用求值函數(shù)時用到變量組合值數(shù)組下標卻是與變量ACS編碼關(guān)于，兩者對不上。解決辦法：在生成變量組合數(shù)時，將zuhe[i]=(n>>i)%2改為zuhe[a[lzp]-65]=(n>>i)%2;七、測試用例、成果及其算法性能分析（一）、初始界面（二）、測試用例及成果(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。（可滿足式）通過測實驗證成果都對的，實現(xiàn)了題目規(guī)定。（三）、算法性能分析1、算法時間性能分析用窮舉法列真值表有2^n（n為變量個數(shù)）種狀況，為每一種狀況所有變量賦值次數(shù)為n,則為所有狀況變量賦值次數(shù)為n*2^n次，即在函數(shù)voidcreatzuhe(intn,intm,chara[])中語句需執(zhí)行n*2^n次，是整個算法當中頻度最大語句，由于算法時間復雜度考慮只是對于問題規(guī)模n增長率，因此該算法時間復雜度為T(n)=O(n*2^n)。2、算法空間性能分析本算法空間復雜度較低，需要一種zuhe[30]數(shù)組來存儲變量取值，一種大小為M數(shù)組存儲邏輯表達式，一種M二叉樹鏈接存儲邏輯表達式構(gòu)成樹結(jié)點。兩個堆棧長度不超過M，因此空間復雜度為O（M）。（四）、經(jīng)驗和體會初拿到本問題，就覺得與學過帶括號算術(shù)表達式計算問題相似。其最核心是算符優(yōu)先級判斷，可以將它類比算術(shù)表達式列出同數(shù)據(jù)構(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、依照提示輸入要鑒別邏輯表達式（表達式中可以有空格）3、輸入表達式后浮現(xiàn)菜單選項，顧客可以選取程序自動窮舉賦值法和顧客賦值法進行鑒別；4、在顯示相應(yīng)成果后，依照提示信息在進行下一步。九、參照文獻[1]王昆侖，李紅.數(shù)據(jù)構(gòu)造與算法.北京：中華人民共和國鐵道出版社，5月。[2]嚴蔚敏，吳偉明.數(shù)據(jù)構(gòu)造.北京：清華大學出版社，5月。[3]李春葆.數(shù)據(jù)構(gòu)造教程.北京：清華大學出版社，5月。[4]蹇強，羅宇.數(shù)據(jù)構(gòu)造.北京：郵電大學出版社，5月。[5]金遠平.《數(shù)據(jù)構(gòu)造》（C++描述.北京：清華大學出版社5月。十、附錄（完整代碼）#include"stdlib.h"http:// 調(diào)用stdlib.h里面函數(shù) `#include"stdio.h"#include"iostream.h"#include"string.h"http://包括字符串解決函數(shù)頭文獻#include"math.h"http://調(diào)用數(shù)學函數(shù)庫#include"iomanip.h"http://是I/O流控制頭文獻#definemaxsize100intzuhe[maxsize]；//變量取值組合數(shù)組定義intN；//變量個數(shù)typedefstructnode//依照表達式建立二叉樹結(jié)點定義{ chardata; structnode*lchild； structnode*rchild;}BiTNode,*bitree;typedefstructstack//辨認表達式使用堆棧定義,它存儲都是樹構(gòu)造{//棧中元素都是樹結(jié)點構(gòu)造 bitree*base；//棧底指針 bitree*top；//棧頂指針 intstacksize；//棧容量}seqstack;voidcreatzuhe(intn,intm,chara[])//生成變量組合數(shù){intlzp=m-1; for(inti=0;i<m;i++) { zuhe[a[lzp]-65]=(n>>i)%2; lzp--; }}voidcreate(bitree&f,bitreel,bitreer)//自底向上地依照運算符地優(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->rchild=NULL; } }}charyouxianji(charm,charn)//邏輯運算符優(yōu)先級鑒別{ inti,j; charbijiao[7][7]={ '','|','&','~','(',')','#'，//二維數(shù)組比較優(yōu)先級先后 '|','>','<','<','<','>','>', '&','>','>','<','<','>','>'， '~','>','>','>','<','>','>', '(','<','<','<','<','=','', ')','>','>','>','','>','>', '#','<','<','<','<','','='}; for(i=0;i<7;i++) if(bijiao[0][i]==m)//找到m運算符列號 break; for(j=0;j<7;j++)//找到n運算符行號 if(bijiao[j][0]==n) break; returnbijiao[j][i]；//返回優(yōu)先級符號:>、<、=}voidsetstack(seqstack&st)//初始化棧{ st.base=(bitree*)malloc(maxsize*sizeof(node)); st.top=st.base； st.stacksize=maxsize；//棧容量}voidpush(seqstack&st,bitreee)//入棧{ if(st.top-st.base<st.stacksize)//符合條件入棧 { *st.top=e; st.top++； } elsecout<<"ERROR!!!"<<endl；//不符合輸出ERROR!!!}voidpop(seqstack&st,bitree&e)//出棧{ if(st.top==st.base)cout<<"ERROR!!!"<<endl；//不符合條件輸出ERROR!!！st.top--；//符合條件e=*st.top;}voidgettop(seqstack&st,bitree&e)//取棧頂元素{ if(st.top==st.base)cout<<"ERROR!!!"<<endl//不符合條件輸出ERROR!!!e=*(st.top-1)；//符合取棧頂元素}voidcreattree(chars[],bitree&tree)//依照邏輯表達式將數(shù)據(jù)存入二叉樹中，定義兩個棧{seqstackvariable；//變量棧seqstacklogic；//邏輯運算符棧setstack(variable)；//變量棧初始化setstack(logic)；//邏輯運算符棧初始化bitreelogic1,variables,logics,e,a,b,g,kuohao;//定義棧中元素,g為最后二叉樹根 logic1=(bitree)malloc(sizeof(node));//分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型logic1->data='#'；//將邏輯運算符棧棧底元素設(shè)為'#'push(logic,logic1)；//將邏輯運算符棧入棧.while(*s!=NULL) { if(int(*s)>=65&&int(*s)<=90)//讀取是變量 { variables=(bitree)malloc(sizeof(node)); //分派構(gòu)造nodesize大小內(nèi)存,強制轉(zhuǎn)換為bitree類型variables->data=*s;push(variable,variables)；//入變量棧 } elseif(int(*s)>90||int(*s)<65)//讀取邏輯運算符 {gettop(logic,e)；//取運算符棧棧頂元素進行優(yōu)先級比較switch(youxianji(*s,e->data)) {case'<'：//棧頂運算符優(yōu)先級低,邏輯運算符進棧 logics=(bitree)malloc(sizeof(node));//強制轉(zhuǎn)換為bitree類型 logics->data=*s; push(logic,logics); break;case'='： pop(logic,kuohao)；//括號并接受下一種字符 break;case'>'：//棧頂運算符優(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);//將暫時根作為新變量壓入變量棧中 gettop(logic,e); if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>') { logics=(bitree)malloc(sizeof(node));//強制轉(zhuǎn)換為bitree類型 logics->data=*s; push(logic,logics)；//邏輯運算符入棧 } elses=s-1; break; } } s++; } tree=g;}intvaluetree(bitreetree)//依照變量取值組合并運用邏輯表達式性質(zhì)對樹進行求值{if(!tree)return0；//遇到空結(jié)點elseif(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//找到是變量 returnzuhe[int(tree->data)-65]；//返回值elseif(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)&&valuetree(tree->rchild)); break;case'~'： return(!valuetree(tree->rchild))； break; default：return0; } elsereturn0;}voiduser(intm,charb[])//顧客輸入變量一組取值狀況{inti;cout<<"請依次輸入你變量取值(0或1)"<<endl;for(i=0;i<m;i++) {cout<<b[i]<<""；//轉(zhuǎn)化為char類型輸出 } cout<<endl; for(i=0;i<m;i++) { cin>>zuhe[b[i]-65]; }}voidprint(){ cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl; cout<<""<<endl;cout<<"你好！"<<endl;cout<<"歡迎使用重言式鑒別軟件！"<<endl;cout<<""<<endl;cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl;}voidmeun()//菜單函數(shù){ system("cls")；//清屏函數(shù) print(); charstr[maxsize],stri[maxsize],*pstr,q,bl[20]; intj,i=0,choose=1,sum,n=0,m=0; bitreeTree; intSUM=0；//用于累加變量每種組合邏輯表達式成果; cout<<"☆☆☆請輸入邏輯表達式表達式:例如(~A|B&C)☆☆"<<endl; scanf("%[^\n]",str)；//讀取包括各種空格邏輯表達式 pstr=str; for(;*pstr!=NULL;pstr++,n++){//邏輯表達式對的讀取, if(str[n]>=97&&str[n]<=122)str[n]=str[n]-32;//將小寫轉(zhuǎn)換成大寫 if(str[n]!='')stri[i++]=*pstr；//去除表達式中空格 } intnu=strlen(stri); for(intk=0;k<nu;k++) if(stri[k]>=65&&stri[k]<=90) { intmark=0；//標記變量 for(intj=0;j<m;j++) { if(bl[j]==stri[k]) { mark=1;break; } } if(mark==0) { bl[m]=str[k]; m++;//m是變量個數(shù) } } sum=int(pow(2,m)); stri[i]='#'；//最后一字符后加入'#',與運算符棧棧底元素'#'相應(yīng) stri[i+1]='\0'；//結(jié)束標志'\0' cout<<"

請選取你要操作

"<<endl;cout<<"

"<<endl;cout<<"

"<<endl;cout<<"

"<<endl;cout<<"

"<<endl; cout<<"

1計算機窮舉法

"<<endl; cout<<"

2顧客自定義給變量賦值

"<<endl; cout<<"

3重新開始

"<<endl; cout<<"

0退出

"<<endl; cout<<"請選取你要操作："；//提示信息 cin>>choose; while(choose!=1&&choose!=2&&choose!=3&&choose!=0) { cout<<"您輸入有誤,請您重新輸入:"；//提示信息 cin>>choose; } switch(choose) { case1://鑒別重言式類別 creattree(stri,Tree)；//建立重言式二叉樹for(j=0;j<sum;j++) { creatzuhe(j,m,bl)；//產(chǎn)生變量取值組合 SUM+=valuetree(Tree)；//SUM累加 }stri[i]='\0'；//加入結(jié)束標志以便輸出邏輯表達式if(SUM==0)