重言式判別課程設(shè)計(jì)報(bào)告樣本

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

請(qǐng)選取你要操作

"<<endl;cout<<"

"<<endl;cout<<"

"<<endl;cout<<"

"<<endl;cout<<"

"<<endl; cout<<"

1計(jì)算機(jī)窮舉法

"<<endl; cout<<"

2顧客自定義給變量賦值

"<<endl; cout<<"

3重新開始

"<<endl; cout<<"

0退出

"<<endl; cout<<"請(qǐng)選取你要操作："；//提示信息 cin>>choose; while(choose!=1&&choose!=2&&choose!=3&&choose!=0) { cout<<"您輸入有誤,請(qǐng)您重新輸入:"；//提示信息 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é)束標(biāo)志以便輸出邏輯表達(dá)式if(SUM==0)