離散數(shù)學實驗報告

1、實 驗 報 告（2016 / 2017 學年 第 一 學期）課程名稱離散數(shù)學實驗名稱利用真值表法求取主析取范式以及主合取范式的實現(xiàn)實 驗 報 告實驗名稱利用真值表法求取主析取范式以及主合取范式的實現(xiàn)指導教師實驗類型驗證實驗學時4實驗時間一、 實驗目的和要求內(nèi)容：編程實現(xiàn)用真值表法求取任意數(shù)量變量的合式公式的主析取范式和主合取范式。要求：能夠列出任意合式公式的真值表并給出相應主析取和主合取范式。二、實驗環(huán)境(實驗設備)X86架構計算機操作系統(tǒng)：Windows 7 32bitIDE: CodeBlokcs 16.02編程語言：C+編譯器：GCC三、實驗原理及內(nèi)容內(nèi)容：編程實現(xiàn)用真值表法求取任意數(shù)量

2、變量的合式公式的主析取范式和主合取范式。原理：先將中綴表達式轉(zhuǎn)換成后綴表達式，再將后綴表達式中每一個字母變量一一賦值，用遞歸枚舉的方法枚舉所有賦值情況，并且用map映射將每一個字母變量與當前被枚舉的值一一映射，對每一種賦值情況調(diào)用后綴表達式計算函數(shù)計算后綴表達式的值，打印真假情況。如果是真，記錄到名為zhen的vector不定長數(shù)組中，如果是假，記錄到名為jia的vector不定長數(shù)組中。最后根據(jù)zhen和jia的不定長數(shù)組來打印主析取范式和主合取范式。 此程序可以實現(xiàn)任意數(shù)量的字母變量的主析取范式求取和主合取范式求取，以及真值表打印。 實 驗 報 告第一步：預處理 預處理，去除中綴表達式中條

3、件->中的>,和雙條件<=>中的= 和 > ，這樣，所有的運算符只是一個字符，后期處理起來更加方便。 void ddd() string:iterator i=zhong.begin(); /string類迭代器，需在頭文件加入#include<string>int flag=1;while(flag) flag=0; for(i=zhong.begin();i!=zhong.end();+i) if(*i='>') zhong.erase(i); flag=1; break; if(*i='=') zhong.e

4、rase(i); flag=1; break; 第二步：將中綴表達式轉(zhuǎn)換后綴表達式 利用棧和優(yōu)先級函數(shù)來將中綴表達式轉(zhuǎn)換成后綴表達式，此函數(shù)另一個功能是將中綴表達式中所有出現(xiàn)過的字母變量都保存包名為alpha的string類中（string類為STL中的string，需要在頭文件加入#include<string>），并且alpha中不出現(xiàn)重復字母，這樣，通過alpha.size()函數(shù)就可以得到所有字母變量的個數(shù)，并且方便后面枚舉賦值映射。全局變量：string zhong; /中綴表達式char hou1000; /后綴表達式string alpha; /存放所有字母變量優(yōu)先級

5、函數(shù)： int icp(char a) /棧外優(yōu)先級if(a='#') return 0;if(a='(') return 12;if(a='!') return 10;if(a='&') return 8;if(a='|') return 6;if(a='-') return 4;if(a='<') return 2;if(a=')') return 1;int isp(char a) /棧內(nèi)優(yōu)先級if(a='#') return 0;

6、if(a='(') return 1;if(a='!') return 11;if(a='&') return 9;if(a='|') return 7;if(a='-') return 5;if(a='<') return 3;if(a=')') return 12; void change() /中綴表達式轉(zhuǎn)換后綴表達式int j=0;stack<char> s; /定義臨時棧，需要在頭文件加入#include <stack>char ch,

7、y;s.push('#');char t1,t2;stringstream ss(zhong); /字符串流，需要在頭文件加入#include <sstream>while(ss>>ch,ch!='#')if(isalpha(ch) /判斷是不是字母，如果是，加入到alpha字符串中houj+=ch; /并且加入到后綴表達式字符串中if(alpha.find(ch)=-1)alpha.push_back(ch);else if(ch=')')for(y=s.top(),s.pop();y!='('y=s.t

8、op(),s.pop()houj+=y;elsefor(y=s.top(),s.pop();icp(ch)<=isp(y);y=s.top(),s.pop()houj+=y;s.push(y);s.push(ch);while(!s.empty()y=s.top();s.pop();if(y!='#')houj+=y;houj='#' 第三步：遞歸枚舉每一個字母變量的取值情況 用深度優(yōu)先搜索（dfs）的思想進行遞歸枚舉，如果當前遞歸深度已經(jīng)達到字符串長度，就說明所有字母已經(jīng)取值成功，字母的“值”用map進行映射（需要在頭文件加入#include<ma

9、p>），所有字母都已經(jīng)枚舉后調(diào)用cal（）函數(shù)對當前取值情況的后綴表達式進行計算，因為map<string,int> M對象是全局變量，所以cal（）函數(shù)可以查看到相應字母的取值情況。 計算完成后，打印真值，如果當前計算結(jié)果是true，那么加入到zhen數(shù)組中，以待后面的主析取范式打印調(diào)用，如果是false，加入到jia數(shù)組，以待后面的主合取范式打印調(diào)用。 全局變量：map<char,int> M; /映射，將字母變量與0或1一一對應struct noteint a100;vector<note> zhen; /不定長數(shù)組，存放主析取范式對應字母變量的

10、01情況，也就是表達式真值為Tvector<note> jia; /不定長數(shù)組，存放主合取范式對應字母變量的01情況，也就是表達式真值是Fvoid dfs(int cur) /遞歸枚舉每一種字符變量的取值情況if(cur=alpha.size()int ans=cal();for(int i=0;i<alpha.size();i+)if(Malphai)printf("Tt");elseprintf("Ft");if(ans=1) /真值為T 計入到zhen數(shù)組，以待后面主析取范式使用printf("Tn");not

11、e t;for(int i=0;i<alpha.size();i+)t.ai=Malphai;zhen.push_back(t);else /真值為F 計入到jia數(shù)組，以待后面主合取范式使用printf("Fn");note t;for(int i=0;i<alpha.size();i+)t.ai=Malphai;jia.push_back(t);return ;Malphacur=1; /深度優(yōu)先搜索（dfs）進行遞歸枚舉dfs(cur+1);Malphacur=0;dfs(cur+1); int cal() /對賦值后的后綴表達式進行計算，返回計算結(jié)果st

12、ack<int> s;char ch;int j=0;int t1,t2;while(1)ch=houj;if(ch='#') break;if(ch=0) break;j+;if(ch>='A'&&ch<='Z')|(ch>='a'&&ch<='z')s.push(Mch);elseif(ch='!')t1=s.top();s.pop();s.push(!t1);else if(ch='&')t1=s.to

13、p();s.pop();t2=s.top();s.pop();if(t1=1&&t2=1)s.push(1);elses.push(0);else if(ch='|')t1=s.top();s.pop();t2=s.top();s.pop();if(t1=0&&t2=0)s.push(0);elses.push(1);else if(ch='-')t1=s.top();s.pop();t2=s.top();s.pop();if(t1=0&&t2=1)s.push(0);elses.push(1);else if(c

14、h='<')t1=s.top();s.pop();t2=s.top();s.pop();if(t1=1&&t2=1)|(t1=0&&t2=0)s.push(1);elses.push(0);int ans=s.top();return ans; 最后一步：打印主析取范式和主合取范式 最后一步，也是最簡單的一步，打印主析取范式和主合取范式，由于前面在遞歸枚舉dfs的過程中已經(jīng)把真值表順帶打印了，所以就只剩下主析取范式和主合取范式了，在dfs過程中，所有取值為真的情況已經(jīng)加入zhen的vector數(shù)組中了，所有取值為假的以及加入到了jia的ve

15、ctor數(shù)組中了，雖然存放的是01序列，但是alpha中字母順序自始至終不變，所以根據(jù)下標可以形成一一對應關系。main 函數(shù) int main()while(true)int i;M.clear();alpha.clear();zhen.clear();jia.clear();printf("或運算為 | , 與運算為 & ,單條件為 -> ,雙條件我 <=> ,非運算為 !n");printf("請輸入表達式,回車結(jié)束n"); cin>>zhong; zhong.append("#"); dd

16、d(); change(); for(i=0;i<alpha.size();i+) printf("%ct",alphai); printf("表達式真值n"); dfs(0); printf("主析取范式為n");int lena=zhen.size();for(i=0;i<lena;i+)if(i!=0) printf("");int *p=zheni.a;printf("(");for(int j=0;j<alpha.size();j+)if(j!=0) printf(&

17、quot;");if(pj=1)printf("%c",alphaj);elseprintf("%c",alphaj);printf(")");printf("n");printf("主合取范式為n");for(i=0;i<jia.size();i+)if(i!=0) printf("");int *p=jiai.a;printf("(");for(int j=0;j<alpha.size();j+)if(j!=0) printf("");if(pj=0)printf("%c",alphaj);elseprintf("%c",alphaj);printf(")");printf("nn"); return 0; 程序測試與分析：由于使用了STL中vector數(shù)組和string 類，所以可以實現(xiàn)計算含有任意數(shù)量的字母變量的表達式。本程序中或運算為 | , 與運算為 & ,單條件為 -> ,雙條件我 <=> ,非運算為 !測試一：輸入P&Q運行截圖： 結(jié)果