程序判定合式公式

1、合式公式的判定1、 基本概念1、合式公式： (1)单个命题常项或变项是合式公式；(2)如果A是合式公式，则A也是合式公式；(3)如果A，B是合式公式，则PQ、PQ、PQ、 PQ也是合式公式； (4)只有有限次地应用(1)(3)所包含的命题变元，联结词和括号的符号串是 合式公式。2、设命题集合Lp:C1,C2,Cn 长度：语言构成元素的数目 表达式u=v:指长度相等且从左向右比处处相等 初始段：从最左端开始向右扫描 结尾段：从最右端开始向左扫描2、 编程思路假定 给定的程序变量为U ，U为Lp 表达式，代表输入的带判定的字符串又记“*”代表“”，“”，“”，“”四种之一。则：1、空表达式不是合适

2、公式的表达式。返回NO2、单独的一个符号是一个公式时，当且仅当此符号为命题符号3、如果U的长度大于1，则U 必须以“（”开头，否则不是合式公式，返回NO。（1）如果U的第二个符号为一个表示否定的“” ，则U必须是可以匹配（V） 模式， 其中V是一个表达式。否则U不是合式公式，即U是合式公式当且仅当V是合式公式。 于是，递归判断V是否为合式公式，转入1、重头开始判断。（2）如果U的第二个符号不是“”。则U一定要符合（A*B）模式。 对U从左向右扫描，遇到“（A”停止，其中A是一个含有相同数目的“（”和“）” 的表达式，如果没有，则U不是合式公式，返回NO。 对U从右向左扫描，遇到“B）”停止，其

3、中B是一个含有相同数目“（”和“）”的 表达式，如果没有，则U不是合式公式，返回NO。 验证（A*B）的“*”是否是“”，“”，“”，“”四种之一，如果不是，则U 不是合式公式，返回NO。 递归判断A，B是否为合式公式，转入1、重头开始判断3、 程序代码#include<stdio.h>#include<string.h>#include<stdlib.h>void check(char *str1);int main(void) int index = 1 ; int keyNum = 1 ;static char string50 ;/ 友好界面，循环使

4、用判断 while( index != 0 ) printf("欢迎使用合式公式判断系统n");printf("合式公式（）不可以省略n");printf("用- 表示非n");printf("用* 表示与n");printf("用+ 表示或n");printf("用> 表示蕴涵n");printf("用 表示等值n");printf("请输入您要判断识别的字符串：n"); scanf("%s",&st

5、ring); check(string); printf("请选择：0-退出系统；1-继续判断其它字符串n"); scanf( "%d", &keyNum ) ;if(keyNum = 0)break;elsecontinue; / 合式公式字符串的判读void check(char *str1)char formal50;int len = 0;/ 获取字符串的长度并且去除空格while( *str1 != '0')if(*str1 != ' ')formallen = *str1;len+;str1+;form

6、allen = '0'printf("字符串%st有效长度:%dn",formal,len);/ 空字符串不是合式公式if(len = 0)printf("字符串为空ntttNO!tt该字符串不是合式公式n");return;/ 单独的一个符号是一个公式时，当且仅当次符号为命题符号else if(len = 1)if(!isalpha(formal0)printf("字符串%s不是合适字母ntttNO!tt该字符串不是合式公式n",formal);return;elseprintf("tttYES!tt字符串

7、%s 是合式公式n",formal);return;/ 如果U的长度大于，则U 必须以“（”开头，否则不是合式公式，返回NO。elseif( (formal0 != '(') | (formallen-1 != ')')printf("字符串%s 没有以“(”开始或者以“)”结束ntttNO!tt该字符串不是合式公式n",formal);return;else/ 如果U的第二个符号为一个表示否定的“”，则U必须是可以匹配（V）模式if(formal1 = '-')char newstring50 ;int i = 0

8、;for(i = 0; i < len - 3; i+)newstringi = formal2+i;newstringi = '0'check(newstring); / 递归判断V是否为合式公式/如果U的第二个符号不是“”。则U一定要符合（A*B）模式。elseint j = 0;int max1 = 0;int max2 = 0;int aindex = 0;int bindex = 0;int prenum = 0;int rearnum = 0;char Astring50 ;char Bstring50 ;/ 对U从左向右扫描，遇到“（A”停止，其中A是一个含

9、有相同数目的“（”和“）”的表达式for(j = 0; j < len; j+)if(formalj = '(')prenum+;max1+;else if(formalj = ')')prenum-;if(prenum = 1 )aindex = j;break;if(prenum = 0 && max1 = 1)prenum+;/ 如果没有，则U不是合式公式，返回NO。if(prenum != 1)printf("字符串%s 中没有扫描到（A ntttNO!tt该字符串不是合式公式n",formal);return

10、;/截取新的短的字符串Aif(max1 = 1)Astring0 = formal1;Astring1 = '0'elsefor(j = 0; j < aindex; j+)Astringj = formal1+j;Astringj = '0'/ 对U从右向左扫描，遇到“B）”停止，其中B是一个含有相同数目“（”和“）”的表达式max2 = 0;for(j = len - 1; j >= 0; j-)if(formalj = ')')rearnum+;max2+;else if(formalj = '(')rearnu

11、m-;if(rearnum = 1)bindex = j;break;if(rearnum = 0 && max2 = 1)rearnum+;/ 如果没有，则U不是合式公式，返回NO。if(rearnum != 1 )printf("字符串%s 中没有扫描到 B）ntttNO!tt该字符串不是合式公式n",formal);return;/截取新的短的字符串Bif(max2 = 1)Bstring0 = formallen-2;Bstring1 = '0'elsefor(j = 0; (bindex + j) < len - 1; j+)

12、Bstringj = formalbindex+j;Bstringj = '0'/ 验证（A*B）的“*”是否是“”，“”，“”，“”四种之一if(max1 = 1 && max2 = 1)if( formal2 = '*' | formal2 = '+' | formal2 = '>' | formal2 = '' )/ 递归判断A，B是否为合式公式check(Astring); check(Bstring);elseprintf("字符串% s中连接符不对ntttNO!tt该字符串不是合式公式n",formal);return;elseif(aindex != bindex - 2)if(max1 != 1 && max2 !=1 )printf("字符串% s中（A*B）不对ntttNO!tt该字符串不是合式公式n",formal);return;if( formalaindex + 1 = '*' | formalaindex + 1 = '+' | formalai