大二上学期时写的代码,用C++实现的。
#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>
#include <vector>
#include<math.h>
using namespace std;
//&表示合取,|表示析取,!表示非,>表示条件,=表示双条件
class ForBase
{
private:
static const int MAXN = 92;
int numVar; //记录范式中的变量
bool variables[MAXN]; //存储变量真假值,初始为F
string sourceFormula; //存储源串
string normalCFormula; //合取串
string normalDFormula; //析取串
vector<char> vctofVar; //向量容器--存储命题单元PQR
vector<char> vctofPoland; //向量容器--存储命题
stack<char> stk; //栈
stack<bool> boolStk; //存储命题中的命题单元
bool isVar(char ch)const; //规定命题是大写英文字母
void addMin(int minterm); //计算布尔小项
void addMax(int maxterm); //计算布尔大项
bool compute(int minterm); //逻辑运算
void getInPod(); //栈操作--将命题公式转换成后序表达式
int countTerms(int n); //求小项/大项个数
void assign(int minterm); //逻辑判断
public:
ForBase(); //构造
~ForBase(); //析构
void getSource(); //输入源式
string getNC(); //获取主析取范式
string getND(); //获取主合取范式
void printSource()
{
cout << sourceFormula << endl;
}
void printDNormal() //打印合取串
{
cout << normalDFormula << endl;
}
void printCNormal() //打印析取串
{
cout << normalCFormula << endl;
}
void printTruthTable(); //打印真值表
};
//构造函数
ForBase::ForBase()
{
for (int i = 0; i<MAXN; i++)
variables[i] = false; //初始化为F
numVar = 0; //个数为0
}
//析构函数
ForBase::~ForBase()
{
while (!stk.empty()) //清除栈
stk.pop();
vctofVar.clear(); //清除向量
vctofPoland.clear(); //清除向量
}
//求小项/大项个数
int ForBase::countTerms(int n) //n为P、Q、R、Y...的个数
{
if (n == 0) //合法性判断
{
cout << "invalid input!" << endl;
exit(0);
}
return pow(2, n);
}
//保证输入的命题为大写英文字母
bool ForBase::isVar(char ch)const
{
if (ch >= 'A'&&ch <= 'Z')
return true;
return false;
}
//输入命题公式
void ForBase::getSource()
{
cout << "Input the source formula:" << endl;
cin >> sourceFormula;
}
//栈操作--将命题公式转换成后序表达式
void ForBase::getInPod()
{
wchar_t temp, temp1;
int len = sourceFormula.size();//获取源命题公式长度
for (int i = 0; i < len; i++)
{
temp = sourceFormula[i]; //获取命题元素
if (isVar(temp)) //命题单元(英文字母)
{
if (!variables[temp]) //真假表中为F
{
numVar++; //变量个数+1
vctofVar.push_back(temp); //串连在命题单元容器末尾
variables[temp] = true; //变化为T
}
vctofPoland.push_back(temp); //串联在命题容器之后
}
else //为操纵符
switch (temp)
{
case'(': //进栈
case'!': //进栈
stk.push(temp);
break;
case'&': //为合取
while (!stk.empty()) //栈不为空
{
if (stk.top() != '(')
{
temp1 = stk.top(); //栈顶元素赋给temp1
vctofPoland.push_back(temp1); //串联在命题向量后
stk.pop(); //出栈
}
else break;
}
stk.push(temp); //进栈
break;
case'|':
while (!stk.empty())
{
temp1 = stk.top();
if (stk.top() == '&' || stk.top() == '!')
{
vctofPoland.push_back(temp1); //串联在命题向量后面
stk.pop(); //操作符出栈
}
else break;
}
stk.push(temp); //操作符进栈
break;
case '>':
while (!stk.empty()) //栈不为空
{
if (stk.top() == '&' || stk.top() == '!' || stk.top() == '|')
{
vctofPoland.push_back(temp1); //串联在命题向量后
stk.pop(); //出栈
}
else break;
}
stk.push(temp); //进栈
break;
case '=':
while (!stk.empty()) //栈不为空
{
if (stk.top() == '&' || stk.top() == '!' || stk.top() == '|' || stk.top() == '>')
{
vctofPoland.push_back(temp1); //串联在命题向量后
stk.pop(); //出栈
}
else break;
}
stk.push(temp); //进栈
break;
case')':
while (!stk.empty())
{
if (stk.top() != '(')
{
temp1 = stk.top();
vctofPoland.push_back(temp1);
stk.pop();
}
else break;
}
if (stk.empty())exit(0); //栈为空,结束
stk.pop();//把左括号pop出去
break;
}
}
while (!stk.empty()) //把剩余全部top出来
{
temp1 = stk.top();
vctofPoland.push_back(temp1);
stk.pop();
}
}
//逻辑赋值
void ForBase::assign(int minterm)
{
int temp = minterm;
for (vector<char>::const_iterator itr = vctofVar.begin(); itr != vctofVar.end(); itr++)
{
variables[(int)*itr] = bool(temp & 1);
temp >> 1;
}
}
//逻辑运算
bool ForBase::compute(int minterm)
{
assign(minterm);
wchar_t temp;
bool valueA, valueB;
vector<char>::const_iterator itr = vctofPoland.begin();
while (itr != vctofPoland.end())
{
temp = *itr;
if (isVar(temp)) //是命题单元
boolStk.push(variables[temp]); //存储在boolstk栈中
else
switch (temp) //是操作符
{
case'&': //合取
{
if (boolStk.size()<2)exit(0); //错误处理
valueA = boolStk.top();
boolStk.pop();
valueB = boolStk.top();
boolStk.pop();
valueA = valueA &&valueB;
boolStk.push(valueA);
break;
}
case'|': //析取
{
if (boolStk.size()<2)exit(0);
valueA = boolStk.top();
boolStk.pop();
valueB = boolStk.top();
boolStk.pop();
valueA = valueA || valueB;
boolStk.push(valueA);
break;
}
case'>': //条件
{
if (boolStk.size()<2)exit(0);
valueA = boolStk.top();
boolStk.pop();
valueB = boolStk.top();
boolStk.pop();
if (valueA == false && valueB == true)
valueA = false;
else
valueA = true;
boolStk.push(valueA);
break;
}
case'=': //双条件
{
if (boolStk.size()<2)exit(0);
valueA = boolStk.top();
boolStk.pop();
valueB = boolStk.top();
boolStk.pop();
if (valueA == valueB)
valueA = true;
else
valueA = false;
boolStk.push(valueA);
break;
}
case'!': //非
{
if (boolStk.empty())exit(0);
valueA = !(boolStk.top());
boolStk.pop();
boolStk.push(valueA);
break;
}
}
itr++;
}
if (boolStk.size() != 1) //保证最后只剩一个元素(结果)
{
cout << "Error in computing the value of minterm" << endl;
exit(0);
}
valueA = boolStk.top();
boolStk.pop();
return valueA;
}
//合成布尔小项
void ForBase::addMin(int minterm)
{
vector<char>::const_iterator itr = vctofVar.begin(); //迭代器指向合取串向量
normalCFormula += '(';
while (itr != vctofVar.end())//保证每个布尔小项包含每一个命题单元
{
if (!variables[(int)*itr])
normalCFormula += '!';
normalCFormula += *itr; //命题单元串联在后面
normalCFormula += '&'; //括号内命题单元是合取符号
itr++;
}
normalCFormula += "\b)|"; //括号间是析取符号
}
//合成布尔大项
void ForBase::addMax(int maxterm)
{
vector<char>::const_iterator itr = vctofVar.begin();
normalDFormula += '(';
while (itr != vctofVar.end())
{
if (variables[(int)*itr])
normalDFormula += '!';
normalDFormula += *itr;
normalDFormula += '|';
itr++;
}
normalDFormula += "\b)&";
}
//获取主析取范式
string ForBase::getNC()
{
if (vctofPoland.size() == 0)//合法判断
getInPod();
int n = countTerms(numVar); //获取布尔小(大)项个数
normalCFormula = ' ';
for (int i = 0; i<n; i++)
{
if (compute(i)) addMin(i); //调用逻辑运算,为真加入到最后结果(剔除永假项)
}
normalCFormula += "\b ";
return normalCFormula;
}
//获取主合取范式
string ForBase::getND()
{
if (vctofPoland.size() == 0)//合法判断
getInPod();
int n = countTerms(numVar);
normalCFormula = ' ';
for (int i = 0; i<n; i++)
{
if (!compute(i)) addMax(i); //调用逻辑运算,为假加入到最后结果(剔除永真项)
}
normalDFormula += "\b ";
return normalDFormula;
}
//输出真值表
void ForBase::printTruthTable()
{
int i = 0;
int count = countTerms(numVar);
cout << " 真值表 \n";
cout << endl;
for (i = 0; i<numVar; i++)cout << vctofVar[i] << '\t';
cout << sourceFormula << endl;
cout << endl;
for (i = 0; i<count; i++)
{
int temp = i;
for (int j = 0; j<numVar; j++)
{
if (bool(temp & 1))cout << "F\t";
else cout << "T\t";
temp = temp >> 1;
}
if (this->compute(i))cout << "F\t";
else cout << "T\t";
cout << '\t' << endl;
cout << endl;
}
}
//主函数
int main()
{
ForBase fb;
fb.getSource();
cout << "主析取范式是:" << fb.getNC() << endl;
cout << "主合取范式是:" << fb.getND() << endl;
fb.printTruthTable();
return 0;
}