离散数学实验报告
- 格式：doc
- 大小：343.50 KB
- 文档页数：25
全局变量：
string zhong; //中缀表达式
char hou[1000]; //后缀表达式
string alpha; //存放所有字母变量
优先级函数：
int icp(char a) //栈外优先级
{
if(a=='#') return 0;
if(a=='(') return 12;
if(a=='!') return 10;
void dfs(int cur) //递归枚举每一种字符变量的取值情况
{
if(cur==alpha.size())
{
int ans=cal();
for(int i=0;i<alpha.size();i++)
{
if(M[alpha[i]])
{
printf("T\t");
}
else
{
printf("F\t");
}
}
if(ans==1) //真值为T计入到zhen数组，以待后面主析取范式使用
{
printf("T\n");
note t;
for(int i=0;i<alpha.size();i++)
{
t.a[i]=M[alpha[i]];
}
zhen.push_back(t);
}
else //真值为F计入到jia数组，以待后面主合取范式使用
{
s.push(M[ch]);
}
else
{
if(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);
}
else
cin>>zhong;
zhong.append("#");
ddd();
change();
for(i=0;i<alpha.size();i++)
{
printf("%c\t",alpha[i]);
}
printf("表达式真值\n");
dfs(0);
printf("主析取范式为\n");
int lena=zhen.size();
此程序可以实现任意数量的字母变量的主析取范式求取和主合取范式求取，以及真值表打印。
实验报告
第一步：预处理
预处理，去除中缀表达式中条件->中的>,和双条件<=>中的=和>，这样，所有的运算符只是一个字符，后期处理起来更加方便。
void ddd()
{
string::iterator i=zhong.begin();//string类迭代器，需在头文件加入#include<string>
{
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!='#')
实验报告
（2016/ 2017学年第一学期）
课程名称
离散数学
实验名称
利用真值表法求取主析取范式以及主合取范式的实现
实验报告
实验名称
利用真值表法求取主析取范式以及主合取范式的实现
指导教师
实验类型
验证
实验学时
4
实验时间
一、实验目的和要求
内容：
编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。
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() //中缀表达式转换后缀表达式
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;
{
printf("F\n");
note t;
for(int i=0;i<alpha.size();i++)
{
t.a[i]=M[alpha[i]];
}
jia.push_back(t);
}
return ;
}
M[alpha[cur]]=1;//深度优先搜索（dfs）进行递归枚举
dfs(cur+1);
M[alpha[cur]]=0;
}
else
{
s.push(0);
}
}
}
}
int ans=s.top();
return ans;
}
最后一步：打印主析取范式和主合取范式
最后一步，也是最简单的一步，打印主析取范式和主合取范式，由于前面在递归枚举dfs的过程中已经把真值表顺带打印了，所以就只剩下主析取范式和主合取范式了，在dfs过程中，所有取值为真的情况已经加入zhen的vector数组中了，所有取值为假的以及加入到了jia的vector数组中了，虽然存放的是01序列，但是alpha中字母顺序自始至终不变，所以根据下标可以形成一一对应关系。
{
hou[j++]=y;
}
}
hou[j]='#';
}
第三步：递归枚举每一个字母变量的取值情况
用深度优先搜索（dfs）的思想进行递归枚举，如果当前递归深度已经达到字符串长度，就说明所有字母已经取值成功，字母的“值”用map进行映射（需要在头文件加入#include<map>），所有字母都已经枚举后调用cal（）函数对当前取值情况的后缀表达式进行计算，因为map<string,int> M对象是全局变量，所以cal（）函数可以查看到相应字母的取值情况。计算完成后，打印真值，如果当前计算结果是true，那么加入到zhen数组中，以待后面的主析取范式打印调用，如果是false，加入到jia数组，以待后面的主合取范式打印调用。
for(i=0;i<lena;i++)
{
if(i!=0) printf("∨");
int *p=zhen[i].a;
printf("(");
for(int j=0;j<alpha.size();j++)
{
if(j!=0) printf("∧");
if(p[j]==1)
{
printf("%c",alpha[j]);
s.pop();
if(t1==0&&t2==1)
{
s.push(0);
}
else
{
s.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);
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;
main函数
int main()
{
while(true)
{
int i;
M.clear();
alpha.clear();
zhen.clear();
jia.clear();
printf("或运算为| ,与运算为& ,单条件为-> ,双条件我<=> ,非运算为!\n");
printf("请输入表达式,回车结束\n");
}
程序测试与分析：
string zhong; //中缀表达式
char hou[1000]; //后缀表达式
string alpha; //存放所有字母变量
优先级函数：
int icp(char a) //栈外优先级
{
if(a=='#') return 0;
if(a=='(') return 12;
if(a=='!') return 10;
void dfs(int cur) //递归枚举每一种字符变量的取值情况
{
if(cur==alpha.size())
{
int ans=cal();
for(int i=0;i<alpha.size();i++)
{
if(M[alpha[i]])
{
printf("T\t");
}
else
{
printf("F\t");
}
}
if(ans==1) //真值为T计入到zhen数组，以待后面主析取范式使用
{
printf("T\n");
note t;
for(int i=0;i<alpha.size();i++)
{
t.a[i]=M[alpha[i]];
}
zhen.push_back(t);
}
else //真值为F计入到jia数组，以待后面主合取范式使用
{
s.push(M[ch]);
}
else
{
if(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);
}
else
cin>>zhong;
zhong.append("#");
ddd();
change();
for(i=0;i<alpha.size();i++)
{
printf("%c\t",alpha[i]);
}
printf("表达式真值\n");
dfs(0);
printf("主析取范式为\n");
int lena=zhen.size();
此程序可以实现任意数量的字母变量的主析取范式求取和主合取范式求取，以及真值表打印。
实验报告
第一步：预处理
预处理，去除中缀表达式中条件->中的>,和双条件<=>中的=和>，这样，所有的运算符只是一个字符，后期处理起来更加方便。
void ddd()
{
string::iterator i=zhong.begin();//string类迭代器，需在头文件加入#include<string>
{
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!='#')
实验报告
（2016/ 2017学年第一学期）
课程名称
离散数学
实验名称
利用真值表法求取主析取范式以及主合取范式的实现
实验报告
实验名称
利用真值表法求取主析取范式以及主合取范式的实现
指导教师
实验类型
验证
实验学时
4
实验时间
一、实验目的和要求
内容：
编程实现用真值表法求取任意数量变量的合式公式的主析取范式和主合取范式。
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() //中缀表达式转换后缀表达式
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;
{
printf("F\n");
note t;
for(int i=0;i<alpha.size();i++)
{
t.a[i]=M[alpha[i]];
}
jia.push_back(t);
}
return ;
}
M[alpha[cur]]=1;//深度优先搜索（dfs）进行递归枚举
dfs(cur+1);
M[alpha[cur]]=0;
}
else
{
s.push(0);
}
}
}
}
int ans=s.top();
return ans;
}
最后一步：打印主析取范式和主合取范式
最后一步，也是最简单的一步，打印主析取范式和主合取范式，由于前面在递归枚举dfs的过程中已经把真值表顺带打印了，所以就只剩下主析取范式和主合取范式了，在dfs过程中，所有取值为真的情况已经加入zhen的vector数组中了，所有取值为假的以及加入到了jia的vector数组中了，虽然存放的是01序列，但是alpha中字母顺序自始至终不变，所以根据下标可以形成一一对应关系。
{
hou[j++]=y;
}
}
hou[j]='#';
}
第三步：递归枚举每一个字母变量的取值情况
用深度优先搜索（dfs）的思想进行递归枚举，如果当前递归深度已经达到字符串长度，就说明所有字母已经取值成功，字母的“值”用map进行映射（需要在头文件加入#include<map>），所有字母都已经枚举后调用cal（）函数对当前取值情况的后缀表达式进行计算，因为map<string,int> M对象是全局变量，所以cal（）函数可以查看到相应字母的取值情况。计算完成后，打印真值，如果当前计算结果是true，那么加入到zhen数组中，以待后面的主析取范式打印调用，如果是false，加入到jia数组，以待后面的主合取范式打印调用。
for(i=0;i<lena;i++)
{
if(i!=0) printf("∨");
int *p=zhen[i].a;
printf("(");
for(int j=0;j<alpha.size();j++)
{
if(j!=0) printf("∧");
if(p[j]==1)
{
printf("%c",alpha[j]);
s.pop();
if(t1==0&&t2==1)
{
s.push(0);
}
else
{
s.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);
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;
main函数
int main()
{
while(true)
{
int i;
M.clear();
alpha.clear();
zhen.clear();
jia.clear();
printf("或运算为| ,与运算为& ,单条件为-> ,双条件我<=> ,非运算为!\n");
printf("请输入表达式,回车结束\n");
}
程序测试与分析：
