实 验 报 告
（2016 / 2017 学年 第 一 学期）
课程名称
离散数学
实验名称
利用真值表法求取主析取范式以及主合取范式的实现
实 验 报 告
实验名称
利用真值表法求取主析取范式以及主合取范式的实现
指导教师
实验类型
验证
实验学时
4
实验时间
一、 实验目的和要求
内容：
编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。
要求：
能够列出任意合式公式的真值表并给出相应主析取和主合取范式。
二、实验环境(实验设备)
X86架构计算机
操作系统：Windows 7 32bit
IDE: CodeBlokcs 16.02
编程语言：C++
编译器：GCC
三、实验原理及内容
内容：
编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。
原理：
先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变量一一赋值，用递归枚举的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
枚举所有赋值情况，并且用map映射将每一个字母变量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表达式计算函数计算后缀表达式的值，打印真假情况。如果是真，记录到名为zhen的vector不定长数组中，如果是假，记录到名为jia的vector不定长数组中。最后根据zhen和jia的不定长数组来打印主析取范式和主合取范式。
此程序可以实现任意数量的字母变量的主析取范式求取和主合取范式求取，以及真值表打印。
实 验 报 告
第一步：预处理
预处理，去除中缀表达式中条件->中的>,和双条件<=>中的= 和 > ，这样，所有的运算符只是一个字符，后期处理起来更加方便。
void ddd()
{
string::iterator i=zhong.begin(); //string类迭代器，需在头文件加入#include
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），并且alpha中不出现重复字母，这样，通过alpha.size()函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。
全局变量：
string zhong; //中缀表达式
char hou[1000]; //后缀表达式
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 s; //定义临时栈，需要在头文件加入#include
char ch,y;
s.push('#');
char t1,t2;
stringstream ss(zhong); //字符串流，需要在头文件加入#include
while(ss>>ch,ch!='#')
{
if(isalpha(ch)) //判断是不是字母，如果是，加入到alpha字符串中
{
hou[j++]=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())
{
hou[j++]=y;
}
}
else
{
for(y=s.top(),s.pop();icp(ch)<=isp(y);y=s.top(),s.pop())
{
hou[j++]=y;
}
s.push(y);
s.push(ch);
}
}
while(!s.empty())
{
y=s.top();
s.pop();
if(y!='#')
{
hou[j++]=y;
}
}
hou[j]='#';
}
第三步：递归枚举每一个字母变量的取值情况
用深度优先搜索（dfs）的思想进行递归枚举，如果当前递归深度已经达到字符串长度，就说明所有字母已经取值成功，字母的“值”用map进行映射（需要在头文件加入#include
浙公网安备 33021202002483