程序判定合式公式.doc

合式公式的判定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、空表达式不是合适公式的表达式。返回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）”停止，其中B是一个含有相同数目“（”和“）”的 表达式，如果没有，则U不是合式公式，返回NO。 验证（A*B）的“*”是否是“”，“”，“”，“”四种之一，如果不是，则U 不是合式公式，返回NO。 递归判断A，B是否为合式公式，转入1、重头开始判断3、 程序代码#include#include#includevoid check(char *str1);int main(void) int index = 1 ; int keyNum = 1 ;static char string50 ;/ 友好界面，循环使用判断 while( index != 0 ) printf(欢迎使用合式公式判断系统n);printf(合式公式（）不可以省略n);printf(用- 表示非n);printf(用* 表示与n);printf(用+ 表示或n);printf(用 表示蕴涵n);printf(用 表示等值n);printf(请输入您要判断识别的字符串：n); scanf(%s,&string); 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+;formallen = 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字符串%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;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是一个含有相同数目的“（”和“）”的表达式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 ;/截取新的短的字符串Aif(max1 = 1)Astring0 = formal1;Astring1 = 0;elsefor(j = 0; j = 0; j-)if(formalj = )rearnum+;max2+;else if(formalj = ()rearnum-;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) | 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 = + | formalaindex +