/*
(1) '!'表示否定
(2) '&'表示合取
(3) '|'表示析取
(4) '>'表示条件
(5) '='表示双条件
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
void IsFormula(char (*str)[50]);//判断是否为合式公式，当串长度>3，调用此函数
bool CheckFormula(char (*str)[50]);//判断是否为合式公式
bool IsConnect(char ch);//判断连接词是否为真
void Move(char *str,int pace,int left);//将字符串进行横向移动
int main()
{
char str[2][50];//定义2行数组，str[0]存放字符串，str[1]做标记
char *str1=(char *)malloc(50*sizeof(char));
char choice;
int i,len;//辅助变量
while(1)
{
printf("(1) '!'表示否定\n(2) '&'表示合取\n(3) '|'表示析取\n(4) '>'表示条件\n(5) '='表示双条件\n");
printf("请输入合式公式：\n");
gets(str1);
len=strlen(str1);
str[0][0]='(';//去空格，且在str[0]的外层加上括号，此时len>=2
i=1;
while( *str1 != '\0' )
{
if(*str1 != ' ')
{
str[0][i] = *str1;
i++;
}
str1++;
}
str[0][i]=')';
str[0][i+1]='\0';
if(CheckFormula(str))//判断合式公式是否为真，且满足只有两种英文字符
printf("合法\n");
else
printf("不合法\n");
printf("是否继续(Y/N)");
choice=getchar();
if(choice=='N'||choice=='n')
break;
getchar();
}
return 0;
}
void Move(char (*str)[50],int pace,int left)//横向移动字符串
{
int i;
str[0][left]='A';
for(i=left+1 ; i<strlen(str[0]) ;i++)
{
str[0][i]=str[0][i+pace];
str[1][i]=str[1][i+pace];
}
str[0][i]=0;
str[1][i]=0;
return ;
}
bool IsConnect(char ch)
{
if((ch == '!') || (ch == '&') || (ch == '|') || (ch == '>') || (ch == '='))
return true;
else
return false;
}
bool CheckFormula(char (*str)[50])
{
int l=0,r=0;//l记录左括号的个数，r记录右括号的个数
int i;//辅助变量
int len=strlen(str[0]);
if(len == 2)//当字符串为空的情况，即为()的情况
return false;
else
for(i=0;i< len ;i++)//判断所有的括号是否配对，且将'('标记为1，将')'标记为2
{
if(str[0][i] == '(')
{
str[1][i]=1;
l++;
}
if(str[0][i] == ')')
{
str[1][i]=2;
r++;
}
}
if( l==r )
{
IsFormula(str);
if(str[0][0] == 'A')
return true;
else
return false;
}
else
return false;
}
void IsFormula(char (*str)[50])//关键函数判断 len>=3 的情况
{
int i,j,k;//辅助变量
int left = 0,right =0;
for(i=0;i<strlen(str[0]);i++)
{
if(str[1][i] == 1)
{
left=i;
}
if(str[1][i] == 2)
{
right=i;
break;
}
}
str[1][left]=0;//用完 right 和 left 之后将其标记为0
str[1][right]=
0;
k=right-left;
for(j=1;j<=k;j++)
{
if( ( str[0][left+j] =='!' && (IsConnect(str[0][left+j-1]) || str[0][left+j-1] =='(' ) && isalpha(str[0][left+j+1]) ) //'!'的左边为连接符或
者'('，右边一定为A
|| ( isalpha(str[0][left+j]) && ( IsConnect(str[0][left+j-1]) || isalpha(str[0][left+j-1]) || str[0][left+j-1] =='(') && ( IsConnect(str[0][left+j+1]) || str[0][left+j+1] ==')')) //'A'的右边为连接符，或者'!'，或者'('，右边为连接符或者右括号
|| ( IsConnect(str[0][left+j]) && isalpha(str[0][left+j-1]) && ( str[0][left+j+1] =='!' || isalpha(str[0][left+j+1])))) //连接符的左边为A，右边为非或者A
continue;
else
break;
}
if(j==k)
{
Move(str,k,left);
}
if(right == strlen(str[0])-1)
return ;
else
IsFormula(str);
}