合式公式的判断 – 源码巴士

什么是合式公式？
(1)原子命题常项或变项是合式公式；
(2)如果A是合式公式，则（-A）也是合式公式（- 表示非）；
(3)如果A，B是合式公式，则（AB）、（A+B）、（A < B）、（ A ~ B）也是合式公式；(此处合取 + 析取 < 代表条件 ~ 代表双条件)
(4)只有有限次地应用(1)～(3)所包含的命题变元，联结词和括号的符号串才是合式公式。
个人思路QAQ：
用字符串输入(注意输入格式:在字符串首尾手动加括号)，依次扫描字符串，遇到“非法”字符跳出循环，字符串能够扫描完则为真
时间复杂度：O(n) 数据不大时，可以在1秒内完成
“非法”字符：
（1）(*P) (+P) (<P) (~P)
（2） (P-)
（3） RT (两个大写字母)
（4）括号不匹配
程序中可能会有bug，希望大佬们多多指教

这道题用递归的话，应该会更好，但我不会用，只能暴力判断了，QAQ

#include<cstdio>
#include<cstring>
const int Max = 100010;
char str[Max];
 //'-\'表示否定联结词，\'*\'表示合取联结词，\'+\'表示析取联结词\n"
int len;//存储字符串的长度
int main()
{
	  printf("'-\'表示否定联结词\n");
	   printf("'*\'表示合取联结词\n");
	    printf("'+\'表示析取联结词\n");
	     printf("'<\'表示条件联结词\n");
	      printf("'~\'表示双条件联结词\n");
     while(~scanf("%s",str+1))
    {
           str[0] = '(';
            len = strlen(str);
            str[len] = ')';
               len++;
            str[len] = '\0';
            int l = 0 ,  r = 0 , m;
            bool flag;
             for(int i = 0; i < len; i++)
            {
            	   if(str[i] == '(')
            	       l++;
            	      if(str[i] == ')')
            	         r++;
			}
             if( l != r)
               flag = false;
             else
             { 
             	for(int i = 1; i < len; i++)
             	{
             		 if(str[i] >= 'A' && str[i] <= 'Z' && len == 3)
             		       flag = true;
             		if(str[i] >= 'A' && str[i] <= 'Z')
             		{
             			   if(str[i+1] >= 'A' && str[i+1] <= 'Z' )
             			   {
             			   	    flag = false;
             			   	    break;
							}
					 }
             	   if( str[i] =='*'||str[i] =='+'||str[i] =='<'||str[i]=='~' )
             	     {
             	     	    if(str[i-1] == '(' )
             	     	    {
             	     	    	  if(str[i+1] >= 'A' && str[i+1] <= 'Z')
             	     	    	  {
             	     	    	  	    flag = false;
             	     	    	  	    break;
									}
							  }
					  }
                   if(str[i]=='(' || str[i] ==')')
					         continue;
					         if(str[i] == '-' && str[i+1] >= 'A' && str[i+1] <= 'Z')
					          {
					          	      flag = true;
							  }
					   if(str[i] >= 'A' && str[i] <= 'Z')
					  {
					  	     if(str[i+1] == '-')
					  	      {
					  	       	   flag = false;
					  	       	   break;
							 }
		                  if(str[i+1] == '*' || str[i+1] == '+'|| str[i+1] == '~'|| str[i+1] =='<')
						  {
						  	      if(str[i+2] >= 'A' && str[i+2] <= 'Z')
						  	       {
						  	       	       flag = true;
									}
						  }    			   	
					  }  			
			    }
			 }
			 if(flag)
			  printf("Yes\n");
			  else
			      printf("N0\n");
     }
          return 0;
}

原文链接：https://blog.csdn.net/Mr_liubai/article/details/78021286