离散数学实验报告.doc
-*实 验 报 告（2016 / 2017 学年 第 一 学期）课程名称离散数学实验名称利用真值表法求取主析取范式以及主合取范式的实现实 验 报 告实验名称利用真值表法求取主析取范式以及主合取范式的实现指导教师实验类型验证实验学时4实验时间一、 实验目的和要求内容：编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。要求：能够列出任意合式公式的真值表并给出相应主析取和主合取范式。二、实验环境(实验设备)X86架构计算机操作系统：Windows 7 32bitIDE: CodeBlokcs 16.02编程语言：C+编译器：GCC三、实验原理及内容内容：编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。原理：先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变量一一赋值，用递归枚举的方法枚举所有赋值情况，并且用map映射将每一个字母变量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表达式计算函数计算后缀表达式的值，打印真假情况。如果是真，记录到名为zhen的vector不定长数组中，如果是假，记录到名为jia的vector不定长数组中。最后根据zhen和jia的不定长数组来打印主析取范式和主合取范式。 此程序可以实现任意数量的字母变量的主析取范式求取和主合取范式求取，以及真值表打印。 实 验 报 告第一步：预处理 预处理，去除中缀表达式中条件->中的>,和双条件<=>中的= 和 > ，这样，所有的运算符只是一个字符，后期处理起来更加方便。 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.erase(i); flag=1; break; 第二步：将中缀表达式转换后缀表达式 利用栈和优先级函数来将中缀表达式转换成后缀表达式，此函数另一个功能是将中缀表达式中所有出现过的字母变量都保存包名为alpha的string类中（string类为STL中的string，需要在头文件加入#include<string>），并且alpha中不出现重复字母，这样，通过alpha.size()函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。全局变量：string zhong; /中缀表达式char hou1000; /后缀表达式string alpha; /存放所有字母变量优先级函数： int icp(char a) /栈外优先级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) /栈内优先级if(a=#) return 0;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() /中缀表达式转换后缀表达式int j=0;stack<char> s; /定义临时栈，需要在头文件加入#include <stack>char ch,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.top(),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=#; 第三步：递归枚举每一个字母变量的取值情况 用深度优先搜索（dfs）的思想进行递归枚举，如果当前递归深度已经达到字符串长度，就说明所有字母已经取值成功，字母的“值”用map进行映射（需要在头文件加入#include<map>），所有字母都已经枚举后调用cal（）函数对当前取值情况的后缀表达式进行计算，因为map<string,int> M对象是全局变量，所以cal（）函数可以查看到相应字母的取值情况。 计算完成后，打印真值，如果当前计算结果是true，那么加入到zhen数组中，以待后面的主析取范式打印调用，如果是false，加入到jia数组，以待后面的主合取范式打印调用。 全局变量：map<char,int> M; /映射，将字母变量与0或1一一对应struct noteint a100;vector<note> zhen; /不定长数组，存放主析取范式对应字母变量的01情况，也就是表达式真值为Tvector<note> jia; /不定长数组，存放主合取范式对应字母变量的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数组，以待后面主析取范式使用printf("Tn");note t;for(int i=0;i<alpha.size();i+)t.ai=Malphai;zhen.push_back(t);else /真值为F 计入到jia数组，以待后面主合取范式使用printf("Fn");note t;for(int i=0;i<alpha.size();i+)t.ai=Malphai;jia.push_back(t);return ;Malphacur=1; /深度优先搜索（dfs）进行递归枚举dfs(cur+1);Malphacur=0;dfs(cur+1); int cal() /对赋值后的后缀表达式进行计算，返回计算结果stack<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.top();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(ch=<)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的过程中已经把真值表顺带打印了，所以就只剩下主析取范式和主合取范式了，在dfs过程中，所有取值为真的情况已经加入zhen的vector数组中了，所有取值为假的以及加入到了jia的vector数组中了，虽然存放的是01序列，但是alpha中字母顺序自始至终不变，所以根据下标可以形成一一对应关系。main 函数 int main()while(true)int i;M.clear();alpha.clear();zhen.clear();jia.clear();printf("或运算为 | , 与运算为 & ,单条件为 -> ,双条件我 <=> ,非运算为 !n");printf("请输入表达式,回车结束n"); cin>>zhong; zhong.append("#"); ddd(); 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("");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数组和string 类，所以可以实现计算含有任意数量的字母变量的表达式。本程序中或运算为 | , 与运算为 & ,单条件为 -> ,双条件我 <=> ,非运算为 !测试一：输入P&Q运行截图： 结果：正确 测试二：输入书上第37页下方例题 (P&Q)|(!P&R) 结果：正确 测试三： 课本39页（4）d） (P->(Q&R)&(!P->(!Q&!R) 测试四 输入A&B&C&D&E 正确 测试五输入课本39页（2）b）P->(Q&R)->S) 正确测试六：输入：课本39页（4）a） (!P|!Q)->(P<=>!Q)正确实 验 报 告四、实验小结（包括问题和解决方法、心得体会、意见与建议等） 五、指导教师评语 成 绩批阅人日 期
