#include<stdio.h>
#include<string>
#include<fstream>
#include<vector>
#include<math.h>
using namespace std;
//定义全局变量
#define N 20
char expp[N]; //用于存储波兰表达式
char number[N]={'0'}; //用于存储不同的变元
int a[N][N]={0}; //用于存放生成的二进制数组
int arraynumber=0; //字符串的长度
int num=0; //用于计算变元的个数
int result[N]={0}; //用于存储真值表的结果
int numberOfstr=0; //字符串的长度
int sp(char c) //判断符号
{
if(c=='!')
return 1;
else
if(c=='&'||c=='|'||c=='@'||c=='$')
return 2;
else
if(c>'A'&&c<'Z')
return 3;
else
if(c=='(')
return 4;
else
if(c==')')
return 5;
else
return 0;
} //end sp()
bool correct(char str[],int n) //判断括号是否匹配
{
char st[N];
int top=0,i=1;
int tag=1;
while(i<=n&&tag)
{
if(str[i]=='(')
{
top++;
st[top]=str[i];
}
if(str[i]==')')
if(st[top]=='(')top--;
else tag=0;
i++;
}
if(top>0)tag=0;
return tag;
}
bool Jurdge(char str[],int n) //判断是否是命题公式
{
int i=1;
if(((sp(str[1])==1)||(sp(str[1])==3)||sp(str[1])==4)&&(sp(str[1])!=sp(str[2])))
{
i++;
while(str[i]!='#')
{
if(sp(str[i])==4||sp(str[i])==5)
i++;
else
if(sp(str[i])==sp(str[i+1]))
break;
else
i++;
} //end while
if(i==numberOfstr)return true;
else
return false;
}//end if
else
return false;
} //END JURDGE()
void Translate(char str[],int n) //转化为逆波兰表达式
{
//define the parameter
char stack[N];
char c;
char temp;
int p=1,q=0,kk=0;
int i,j,t,top=0;
t=1;i=1;
c=str[i];i++;
while(c!='#')
{
if(c>='A'&&c<='Z') //判定为命题变元
{
expp[t]=c;
t++;
}
else
if(c=='(') //判定为左括号
{
top++;stack[top]=c;
}
else
if(c==')') //判定为右括号
{
while(stack[top]!='(')
{
expp[t]=stack[top];top--;t++;
}
top--;
}
else //判定为是“等价”或者是“蕴涵”
if(c=='$'||c=='@')
{
while(top!=0&&stack[top]!='(')
{
expp[t]=stack[top];top--;t++;
}
top++;stack[top]=c;
}
else //判定为是“与”或者为“或”
if(c=='&'||c=='|')
{
while(top=='&'||stack[top]=='|')
{
expp[t]=stack[top];top--;t++;
}
top++;stack[top]=c;
}
else //判定“非”
if(c=='!')
{
expp[t]=c;t++;
}
c=str[i];i++;
}
while(top!=0)
{
expp[t]=stack[top];t++;top--;
}
expp[t]='#';
arraynumber=t;
//for(j=1;j<=t;j++)
// printf("%c",expp[j]);
for(j=1;j<=t;j++)
if(expp[j]=='!')
{temp=expp[j];expp[j]=expp[j+1];expp[j+1]=temp;j++;}
printf("波兰表达式如下：\n");
for(j=1;j<=t;j++)
printf("%c",expp[j]);
printf("\n");
} //end translate
void find(char a[],int n) //查找变元个数
{
int i=0,k=0;
i++;
while(a[i]!='#')
{
if(a[i]>='A'&&a[i]<='Z')
{
number[k]=a[i];
k++;
}
i++;
}
for(int j=0;j<k;j++)
{
for(int m=j+1;m<k;m++)
if(number[j]==number[m])
{
for(int l=m;l<k;l++)
number[l]=number[l+1];
k--;
}
}
num=k;
printf("根据变元个数自动生成的二进制表如下:\n");
for(int jj=0;jj<k;jj++)
printf("%3c",number[jj]);
printf("\n");
} //end find
void Binary(int num) //生成二进制数组
{
int x=pow(2,num);
//int y=x;
int r=0;
int temp,i;
for(int j=1;j<x;j++)
{
i=0;r=j;
while(r!=0)
{
temp=r/2;
a[j][i]=r%2;
r=temp;
i++;
}
}
for(int ii=0;ii<x;ii++)
{
for(int jj=num-1;jj>=0;jj--)
printf("%2d ",a[ii][jj]);
printf("\n");
}
} //end Binary()
/*int cal(char c,int p,int q) //计算真值
{
switch(c)
{
case'!':return(!q);break;
case'&':return(p&q);break;
case'|':return(p||q);break;
case'@':return(!p||q);break;
case'$':return(!((!p||q)^(p||!q)));break;
default:return 0;
}
} //calculate()*/
void compvalue() //求波兰表达式的值
{
int stack[N]={0},d;
char c;
int t,top;
int x=pow(2,num);
//printf("num=%d",num);
//int j;
printf("公式的真值表结果如下：\n");
for(int ii=0;ii<x;ii++)
{
top=0;t=1;
c=expp[t];t++;
while(c!='#')
{
if(c>='A'&&c<='Z')
{
for(int j=0;j<num;j++)
if(c==number[j])
d=a[ii][num-j-1];
printf("d=%d ",d);
top++;
stack[top]=d;
//printf("---------------------------------%d\n",stack[top]);
} //end if
else
{
//printf("here!\n");
//stack[top-1]=cal(c,stack[top-1],stack[top]);
switch(c)
{
case'!':stack[top]=!stack[top];top++;break;
case'&':stack[top-1]=stack[top-1]&stack[top];break;
case'|':stack[top-1]=stack[top-1]||stack[top];break;
case'@':stack[top-1]=!stack[top-1]||stack[top];break;
case'$':stack[top-1]=!((!stack[top-1]||stack[top])^(!stack[top]||stack[top-1]));break;
//default:return 0;
}
top--;
} //end else
c=expp[t];t++;
}//end while
printf("------>");
result[ii]=stack[top];
printf("%2d\n",result[ii]);
}
printf("\n");
}
/*void Input(char str[],int n) //输入
{
int j;
vector<string> v;
ifstream in("format.txt");
string line;
while(getline(in,line))
v.push_back(line);
for(int i=0;i<v.size();i++)
{
for(j=0;j<=v[i].size();j++)
{
str[j+1]=v[i][j];
//printf("str[%d]=%c\n",j,str[j]);
}
numberOfstr=j-1;
}
}*/
void input2(char str[],int n) //输入
{
int i=0;
for(int j=0;j<n;j++)
str[j]='*';
printf("please input now:");
//scanf("%c",&str[1]);
do
{
i++;
scanf("%c",&str[i]);
if(str[i]=='\n')i--;
}while(str[i]!='#');
numberOfstr=i;
} //end of input2()
void main() //主函数
{
char str[N];
//char ch='y';
//int flag=1;
//while(flag!=0)
// {
printf("******Welcome to the exprience!****\n");
printf("***********************************\n");
printf("*******请按以下规则输入：**********\n");
printf("*******0.输入的变元在'A'~'Z'之间***\n");
printf("*******1.'!'-->'﹁' **********\n");
printf("*******2.'&'-->'∧' **********\n");
printf("*******3.'|'-->'ˇ' **********\n");
printf("*******4.'@'-->'→' **********\n");
printf("*******5.'$'-->'<->' **********\n");
printf("*******6.'()'-->可以使用括号*******\n");
printf("*******7.'#'-->必须以此作为结束符!*\n");
printf("***********************************\n");
input2(str,N);
/*for(int j=0;j<=numberOfstr;j++) //输出
{
printf("str[%d]=%c\n",j,str[j]);
}*/
while(1)
{
if(correct(str,numberOfstr))
{
if(Jurdge(str,numberOfstr))
{
printf("恭喜你，输入正确!\n");
break;
}
else
{
printf("对不起，你的输入变元或者联结词有误，请重新输入!\n");
input2(str,N);
}
}
else
{
printf("对不起，你输入的表达式括号不匹配，请重新输入!\n");
input2(str,N);
}
}
Translate(str,numberOfstr);
find(expp,arraynumber);
Binary(num);
compvalue();
//printf("是否继续测试?(y/n)");
//scanf("%c",&ch);
//if(ch=='y')flag=1;
// else flag=0;
//}//end while
}
//测试用例
//错误用例
//(P&Q#
//(PP&Q)#
//正确用例
//(!P&Q)#
//P&Q#
//P|Q#
//(P@((!P$Q)&R))|Q#
