离散数学实验报告Word下载.docx
《离散数学实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《离散数学实验报告Word下载.docx（15页珍藏版）》请在冰点文库上搜索。
此程序可以实现任意数量的字母变量的主析取范式求取和主合取范式求取，以及真值表打印。
第一步：
预处理
预处理，去除中缀表达式中条件->
中的>
和双条件<
=>
中的=和>
，这样，所有的运算符只是一个字符，后期处理起来更加方便。
voidddd（）
{
string:
:
iteratori=zhong.begin（）;
//string类迭代器，需在头文件加入#include<
string>
intflag=1;
while（flag）
{
flag=0;
for（i=zhong.begin（）;
i!
=zhong.end（）;
++i）
if（*i=='
>
'
）
zhong.erase（i）;
flag=1;
break;
}
='
}
第二步：
将中缀表达式转换后缀表达式
利用栈和优先级函数来将中缀表达式转换成后缀表达式，此函数另一个功能是将中缀表达式中所有出现过的字母变量都保存包名为alpha的string类中（string类为STL中的string，需要在头文件加入#include<
），并且alpha中不出现重复字母，这样，通过alpha.size（）函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。
全局变量：
stringzhong;
//中缀表达式
charhou[1000];
//后缀表达式
stringalpha;
//存放所有字母变量
优先级函数：
inticp（chara）//栈外优先级
if（a=='
#'
）return0;
（'
）return12;
!
）return10;
&
）return8;
|'
）return6;
-'
）return4;
<
）return2;
）'
）return1;
}
intisp（chara）//栈内优先级
）return11;
）return9;
）return7;
）return5;
）return3;
voidchange（）//中缀表达式转换后缀表达式
intj=0;
stack<
char>
s;
//定义临时栈，需要在头文件加入#include<
stack>
charch,y;
s.push（'
）;
chart1,t2;
stringstreamss（zhong）;
//字符串流，需要在头文件加入#include<
sstream>
while（ss>
ch,ch!
if（isalpha（ch））//判断是不是字母，如果是，加入到alpha字符串中
{
hou[j++]=ch;
//并且加入到后缀表达式字符串中
if（alpha.find（ch）==-1）
{
alpha.push_back（ch）;
}
}
elseif（ch=='
for（y=s.top（）,s.pop（）;
y!
;
y=s.top（）,s.pop（））
hou[j++]=y;
else
icp（ch）<
=isp（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<
map>
），所有字母都已经枚举后调用cal（）函数对当前取值情况的后缀表达式进行计算，因为map<
string,int>
M对象是全局变量，所以cal（）函数可以查看到相应字母的取值情况。
计算完成后，打印真值，如果当前计算结果是true，那么加入到zhen数组中，以待后面的主析取范式打印调用，如果是false，加入到jia数组，以待后面的主合取范式打印调用。
map<
char,int>
M;
//映射，将字母变量与0或1一一对应
structnote
inta[100];
};
vector<
note>
zhen;
//不定长数组，存放主析取范式对应字母变量的01情况，也就是表达式真值为T
jia;
//不定长数组，存放主合取范式对应字母变量的01情况，也就是表达式真值是F
voiddfs（intcur）//递归枚举每一种字符变量的取值情况
if（cur==alpha.size（））
intans=cal（）;
for（inti=0;
i<
alpha.size（）;
i++）
if（M[alpha[i]]）
printf（"
T\t"
else
F\t"
if（ans==1）//真值为T计入到zhen数组，以待后面主析取范式使用
printf（"
T\n"
notet;
for（inti=0;
t.a[i]=M[alpha[i]];
zhen.push_back（t）;
else//真值为F计入到jia数组，以待后面主合取范式使用
F\n"
jia.push_back（t）;
return;
M[alpha[cur]]=1;
//深度优先搜索（dfs）进行递归枚举
dfs（cur+1）;
M[alpha[cur]]=0;
intcal（）//对赋值后的后缀表达式进行计算，返回计算结果
int>
charch;
intt1,t2;
while
（1）
ch=hou[j];
if（ch=='
）break;
if（ch==0）break;
j++;
if（（ch>
A'
ch<
Z'
）||（ch>
a'
z'
））
s.push（M[ch]）;
if（ch=='
t1=s.top（）;
s.pop（）;
s.push（!
t1）;
elseif（ch=='
t2=s.top（）;
if（t1==1&
t2==1）
{
s.push
（1）;
}
else
s.push（0）;
if（t1==0&
t2==0）
if（（t1==1&
t2==1）||（t1==0&
t2==0））
intans=s.top（）;
returnans;
最后一步：
打印主析取范式和主合取范式
最后一步，也是最简单的一步，打印主析取范式和主合取范式，由于前面在递归枚举dfs的过程中已经把真值表顺带打印了，所以就只剩下主析取范式和主合取范式了，在dfs过程中，所有取值为真的情况已经加入zhen的vector数组中了，所有取值为假的以及加入到了jia的vector数组中了，虽然存放的是01序列，但是alpha中字母顺序自始至终不变，所以根据下标可以形成一一对应关系。
main函数
intmain（）
while（true）
inti;
M.clear（）;
alpha.clear（）;
zhen.clear（）;
jia.clear（）;
printf（"
或运算为|,与运算为&
单条件为->
双条件我<
非运算为!
\n"
请输入表达式,回车结束\n"
cin>
zhong;
zhong.append（"
#"
ddd（）;
change（）;
for（i=0;
%c\t"
alpha[i]）;
表达式真值\n"
dfs（0）;
主析取范式为\n"
intlena=zhen.size（）;
lena;
if（i!
=0）printf（"
∨"
int*p=zhen[i].a;
（"
for（intj=0;
j<
j++）
if（j!
∧"
if（p[j]==1）
printf（"
%c"
alpha[j]）;
￢%c"
）"
主合取范式为\n"
jia.size（）;
int*p=jia[i].a;
if（p[j]==0）
\n\n"
return0;
程序测试与分析：
由于使用了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）
（（Q&
R）->
S）
测试六：
输入：
课本39页（4）a）（!
P|!
Q）->
（P<
Q）
四、实验小结（包括问题和解决方法、心得体会、意见与建议等）
五、指导教师评语
成绩
批阅人
日期
升级会员 