C++求任意一个命题公式的真值表，并根据真值表求主范式?
C++求任意一个命题公式的真值表，并根据真值表求主范式?
C++求任意一个命题公式的真值表，并根据真值表求主范式?
求任意一个给定命题表达式的真值表，并根据真值表给出主范式。
求任意一个给定命题表达式的真值表，并根据真值表给出主范式。
#include <string>
#include <stack>
#include <vector>
#include<iostream>
using namespace std;
class formulaBase
{
private:
int numVar;//The number of the variables in the formula
bool variables[100];//To store the value of the variables
string sourceFormula;
string normalCFormula;
string normalDFormula;
string dualFormula;
vector<char> vctofVar;
vector<char> vctofPoland;
stack<char> stk;
bool isVar(char ch)const;
void addMin(int minterm);
void addMax(int maxterm);
bool compute(int minterm);
void getInversePoland();
int countTerms(int n);
void assign(int minterm);
stack<bool> boolStk;
public:
formulaBase();
formulaBase(const formulaBase& rhs);
~formulaBase();
void getSource();
string generateNormalC();
string generateNormalD();
string getDual();
void printSource()const{cout<<sourceFormula<<endl;}
void printDNormal()const{cout<<normalDFormula<<endl;}
void printCNormal()const{cout<<normalCFormula<<endl;}
void printDual()const{cout<<dualFormula<<endl;}
//void printTruthTable();
};
formulaBase::formulaBase()
{
for(int i=0;i<100;i++)variables[i]=false;
numVar=0;
}
formulaBase::formulaBase(const formulaBase& rhs)
{
sourceFormula=rhs.sourceFormula;
for(int i=0;i<100;i++)variables[i]=false;
numVar=0;
}
formulaBase::~formulaBase()
{
while(!stk.empty())stk.pop();
vctofVar.clear();
vctofPoland.clear();
}
int formulaBase::countTerms(int n)
{
if(n==0)
{
cout<<"invalid input!"<<endl;
exit(0);
}
switch(n)
{
case 1:return 2;
case 2:return 4;
default:
{
int tempA=2,tempB=2, i, j;
for(i=2;i<=n;i*=2)tempA*=tempA;
i/=2;
if(i==n)return tempA;
i=n-i;
for(j=2;j<=i;j*=2)tempB*=tempB;
for(j/=2;j<i;j++)tempB*=2;
tempB*=tempA;
return tempB;
}
}
}
bool formulaBase::isVar(char ch)const
{
if (ch>='A'&&ch<='Z')
return true;
return false;
}
void formulaBase::getSource()
{
cout<<"Input the source formula:"<<endl;
cin>>sourceFormula;
/*if(!isValid(sourceFormula))
cout<<"Invalid input !"
"Operate again:"<<endl;
cin>>sourceFormula;*/
}
void formulaBase::getInversePoland()
{
char temp,temp1;
for(int i=0;sourceFormula[i]!='\0';i++)
{
temp=sourceFormula[i];
if(isVar(temp))
{
if(!variables[temp])
{
numVar++;
vctofVar.push_back(temp);
variables[temp]=true;
}
vctofPoland.push_back(temp);
}
else
switch(temp)
{
case'_':case'$': //
case'%':case'#':
case'@':
while(!stk.empty())
{
if(stk.top()==temp)
{
vctofPoland.push_back(temp);
stk.pop();
}
else break;
}
stk.push(temp);
break;
case '(':case '!':
stk.push(temp);
break;
case '+':
while (!stk.empty())
{
if(stk.top()!='(')
{
temp1=stk.top();
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()!='(')
{
temp1=stk.top();
vctofPoland.push_back(temp1);
stk.pop();
}
else break;
}
if(stk.empty())exit(0);
stk.pop();//pop the operator '('
break;
}
}
while(!stk.empty())
{
temp1=stk.top();
vctofPoland.push_back(temp1);
stk.pop();
}
}
void formulaBase::assign(int minterm)
{
int temp=minterm;
vector<char>::const_iterator itr=vctofVar.begin();
for(;itr!=vctofVar.end();itr++)
{
variables[*itr]=bool(temp&1);
temp=temp>>1;
}
}
bool formulaBase::compute(int minterm)
{
assign(minterm);
char temp;
bool valueA,valueB;
vector<char>::const_iterator itr=vctofPoland.begin();
while (itr!=vctofPoland.end())
{
temp=*itr;
if(isVar(temp))boolStk.push(variables[temp]);
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.empty())exit(0);
valueA=!(boolStk.top());
boolStk.pop();
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();
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();
valueA=(!valueA&&valueB)||(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)||(!valueA&&!valueB);
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 formulaBase::addMin(int minterm)
{
int temp=minterm;
vector<char>::const_iterator itr=vctofVar.begin();
normalCFormula+='(';
while (itr!=vctofVar.end())
{
if(!variables[*itr])
normalCFormula+='!';
normalCFormula+=*itr;
normalCFormula+='*';
itr++;
}
normalCFormula+="\b)+";
}
void formulaBase::addMax(int maxterm)
{
int temp=maxterm;
vector<char>::const_iterator itr=vctofVar.begin();
normalDFormula+='(';
while (itr!=vctofVar.end())
{
if( variables[*itr])
normalDFormula+='!';
normalDFormula+=*itr;
normalDFormula+='+';
itr++;
}
normalDFormula+="\b)*";
}
string formulaBase::generateNormalC()
{
if(vctofPoland.size()==0)//This oeration has not been done yet!
getInversePoland();
cout<<"Here!"<<endl;
int n=countTerms(numVar);
cout<<n<<"countTerms"<<endl;
normalCFormula=' ';
for(int i=0;i<n;i++)
{
if(compute(i))addMin(i);
}
normalCFormula+="\b ";
return normalCFormula;
}
string formulaBase::generateNormalD()
{
if(vctofPoland.size()==0)//This operation has not been done yet!!
getInversePoland();
int n=countTerms(numVar);
normalDFormula=' ';
for(int i=0;i<n;i++)
{
if(!compute(i))addMax(i);
}
normalDFormula+="\b ";
return normalDFormula;
}
string formulaBase::getDual()
{
int i=0;
char temp;
dualFormula=' ';
while ((temp=sourceFormula[i])!='\0')
{
switch(temp)
{
case '!':
{
i++;
dualFormula+=sourceFormula[i];
break;
}
case '+':dualFormula+='*';break;
case '*':dualFormula+='+';break;
case'(':case ')':dualFormula+=sourceFormula[i];
break;
default:
if (isVar(temp))
{
dualFormula+='!';
dualFormula+=temp;
}
else
{
cout<<"Error!"<<endl;
exit(0);
}
}
i++;
}
return dualFormula;
}
/*void formulaBase::printTruthTable()//A const function is unable to call a nonconst function!!!
{
int i=0;
int count=countTerms(numVar);
cout<<" TRUTH TABLE \n";
for( i=0;i<=numVar;i++)cout<<"___";
cout<<endl;
//for( i=0;i<numVar;i++)cout<<'|'<<vctofVar[i];
//cout<<"|F|" <<endl;
for( i=0;i<=numVar;i++)cout<<"___";
cout<<endl;
for(i=0;i<count;i++ )
{
int temp=i;
for(int j=0;j<numVar;j++)
{
if(bool(temp&1))cout<<"|1";
else cout<<"|0";
temp=temp>>1;
}
if(this->compute(i))cout<<"|1";
else cout<<"|0";
cout<<'|'<<endl;
for( int k=0;k<=numVar;k++)cout<<"___";
cout<<endl;
}
}
*/
int main()
{
string str;
formulaBase f;
f.getSource();
str=f.generateNormalC();
cout<<"NORMALc:"<<str<<endl;
str=f.generateNormalD();
cout<<"NORMALd"<<str<<endl;
// cout<<"Coming here"<<endl;
//f.printTruthTable();
str=f.getDual();
f.printDual();
return 0;
}