离散数学实验报告
别妄想泡我
544次浏览
2021年01月30日 01:17
最佳经验
本文由作者推荐
海伦凯勒简介-闲庭信步
-*
实
验
报
告
（
2016
/ 2017
学年
第
一
学期）
课程名称
离散数学
实验名称
利用真值表法求取主析取范式以及主合取范
式的实现
-*
实
验
报
告
实验名称
利用真值表法求取主析取范式
以及主合取范式的实现
实验类型
验证
实验学时
4
实验时间
指导教师
一、
实验目的和要求
内容：
编程实现用真值表法求取任意数量变量的合式公式的主析取范式
和主合取范式。
要求：
能够列出任意合式公式的真值表并给出相应主析取和主合取范
式。
二、
实验环境
(
实验设备
)
X86
架构计算机
操作系统：
Windows 7
32bit
IDE: CodeBlokcs 16.02
编程语言：
C++
编译器：
GCC
-*
三、实验原理及内容
内容：
编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主
合取范式。
原理：
先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变
量一一赋值，用递归枚举的方法枚举所有赋值情况，并且用
map
映射将每
一个字母变 量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表
达式计算函数计算后缀表达式的值，打印真 假情况。如果是真，记录到名
为
zhen
的
vector
不定长数组 中，
如果是假，
记录到名为
jia
的
vector
不定长< br>数组中。
最后根据
zhen
和
jia
的不定长数组来打印主析 取范式和主合取范式。
此程序可以实现任意数量的字母变量的主析取范 式求取和主合取范式
求取，以及真值表打印。
-*
实
验
报
告
-*
第一步：预处理
预处理，去除中缀表达式中条件->
中的
>,
和双条件
<=>
中的
=
和
>
，这样，
所有的运算符只是一个字符，后期处理起来更加方便。
void ddd()
{
string::iterator
i=();
//str ing
类
迭
代
器
，
需
在
头
文件
加
入
#include
int flag=1;
while(flag)
{
flag=0;
for(i=();i!=();++i)
{
if(*i=='>')
{
(i);
flag=1;
break;
}
if(*i=='=')
{
(i);
-*
flag=1;
break;
}
}
}
}
第二步：将中缀表达式转换后缀表达式
利用栈和优先级函数来将中缀表达式转换成后缀表达式，此函数另一个功能
是将中缀 表达式中所有出现过的字母变量都保存包名为
alpha
的
string
类中
（
string
类为
STL
中的
string
，< br>需要在头文件加入
#include
）
，
并且
alpha
中不出现重复字母，
这样，
通过
()
函数就可以得到所 有字母变量的个
数，并且方便后面枚举赋值映射。
全局变量：
string zhong;
//
中缀表达式
char hou[1000];
//
后缀表达式
string alpha;
//
存放所有字母变量
优先级函数：
int icp(char a)
//
栈外优先级
-*
{
}
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;
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;
}
-*
void change()
//
中缀表达式转换后缀表达式
{
int j=0;
stack
//
定义临时栈，需要在头文件加入
#include
char ch,y;
('#');
char t1,t2;
stringstream ss(zhong);
//
字符串流，需要在头文件加入
#include
while(ss>>ch,ch!='#')
{
if(isalpha(ch))
//
判断是不是字母，如果是，加入到
alpha
字符串中
{
}
else if(ch==')')
{
hou[j++]=ch;
//
并且加入到后缀表达式字符串中
if((ch)==-1)
{
}
_back(ch);
-*
}
}
for(y=(),();y!='(';y=(),())
{
}
hou[j++]=y;
else
{
}
for(y=(),();icp(ch)<=isp(y);y=(),())
{
}
(y);
(ch);
hou[j++]=y;
while(!())
{
y=();
();
if(y!='#')
{
hou[j++]=y;
-*
}
}
hou[j]='#';
}
第三步：递归枚举每一个字母变量的取值情况
用深度优先搜索（
dfs
）的思想进行递归枚举，如 果当前递归深度已经达到字
符串长度，就说明所有字母已经取值成功，字母的
“
值”
用
map
进行映射（需
要在头文件加入
#include
）
，所有字母都已经枚举后调用
cal
（）函数对
当前取值情 况的后缀表达式进行计算，因为
map
M
对象是全局变< br>量，所以
cal
（）函数可以查看到相应字母的取值情况。
计算完成 后，打印真
值，如果当前计算结果是
true
，那么加入到
zhen
数组中，以待后面的主析取
范式打印调用，如果是
false
，加入到
jia
数组，以待后面的主合取范式打印调
用。
全局变量：
map
//
映射，将字母变量与
0
或
1
一一对应
struct note
{
};
vector
//
不定长数组，存放主析取范式对应字母变量的
01
情况，
也就是表达式真值为
T
int a[100];
-*
vector
jia;
//
不定长数组，存放主 合取范式对应字母变量的
01
情况，
也就是表达式真值是
F
void dfs(int cur)
//
递归枚举每一种字符变量的取值情况
{
if(cur==())
{
int ans=cal();
for(int i=0;i<();i++)
{
}
if(ans==1)
//
真值为
T
计入到
zhen
数组，以待后面主析取范式使用
{
printf(
if(M[alpha[i]])
{
}
else
{
}
printf(
printf(
-*
}
}
note t;
for(int i=0;i<();i++)
{
}
_back(t);
t.a[i]=M[alpha[i]];
else
//
真值为
F
计入到
jia
数组，以待后面主合取范式使用
{
}
return
printf(
note t;
for(int i=0;i<();i++)
{
}
_back(t);
t.a[i]=M[alpha[i]];
M[alpha[cur]]=1;
//
深度优先搜索（
dfs
）进行递归枚举
dfs(cur+1);
M[alpha[cur]]=0;