程序判定合式公式

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

2、：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是一个含有相同数目的“(”和“)” 的表达式，如果没有，则

3、 U 不是合式公式，返回 NO。 对U从右向左扫描，遇到“ B)”停止，其中B是一个含有相同数目“(”和“)”的 表达式，如果没有，则 U 不是合式公式，返回 NO。 验证(A*B )的“ * ”是否是“A” ，“V”，“ ? ”四种之一，如果不是，则U不是合式公式，返回 NO。 递归判断 A， B 是否为合式公式，转入 1、重头开始判断三、程序代码#include <stdio.h>#include <string.h>#include <stdlib.h>void check（ char *str1）;int main（ void ）int index

4、= 1 ;int keyNum = 1 ;static char string50 ;/ 友好界面，循环使用判断while （ index != 0 ）printf（ " 欢迎使用合式公式判断系统 n" ）;printf（ " 合式公式（）不可以省略 n" ）;printf（"用-表示非n"）;printf（"用 * 表示与 A n"）;printf（"用 + 表示或 V n"）;printf（"用 > 表示蕴涵Tn”）；printf（"用表示等值n"）;pr

5、intf（ "请输入您要判断识别的字符串： n" ）;scanf（ "%s",&string）;check（string）;printf（"请选择： 0- 退出系统； 1- 继续判断其它字符串 n" ）;scanf（ "%d", &keyNum ） ;if （keyNum = 0）break ;else continue ;/ 合式公式字符串的判读void check( char *str1)char formal50;int len = 0;/ 获取字符串的长度并且去除空格while ( *str

6、1 != '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(&qu

7、ot;字符串S不是合适字母ntttNO!tt该字符串不是合式公式 n" ,formal);return ;elseprintf( "tttYES!tt 字符串 %s 是合式公式 n" ,formal);return/如果U的长度大于，则U必须以(”幵头，否则不是合式公式，返回NOelseif ( (formal0 != '(' ) | (formallen-1 != ')' )printf("字符串%s没有以“”幵始或者以“”结束ntttNO!tt 该字符串不是合式公式 n" ,formal);return ;e

8、lse/如果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 =

9、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+;/如果没有，

10、则U不是合式公式，返回NOif (prenum != 1)printf( "字符串 %s 中没有扫描到( A ntttNO!tt 该字符串不是合式公式 n" ,formal);return ;/ 截取新的短的字符串 Aif (max1 = 1)Astring0 = formal1;Astring1 = '0' ;elsefor (j = 0; j < aindex; j+)Astringj = formal1+j;Astringj = '0' ;/对U从右向左扫描，遇到B)”停止，其中B是一个含有相同数目 “( ”和“) ”的表达式ma

11、x2 = 0;for (j = len - 1; j >= 0; j-)if (formalj = ')' )rearnum+;max2+;else if (formalj = '(' )rearnum-;if (rearnum = 1)bindex = j;break ;if (rearnum = 0 && max2 = 1)rearnum+;/如果没有，则U不是合式公式，返回NOif (rearnum != 1 )printf( "字符串 %s 中没有扫描到 B )ntttNO!tt 该字符串不是合式公式 n" ,f

12、ormal);return ;/ 截取新的短的字符串 Bif (max2 = 1)Bstring0 = formallen-2;Bstring1 = '0' ;elsefor (j = 0; (bindex + j) < len - 1; j+)Bstringj = formalbindex+j;Bstringj = '0' ;/验证(A*B)的“”是否是“2”T “四种之一if (max1 = 1 && max2 = 1)if ( formal2 ='*' |formal2 ='+' |formal2 =&

13、#39;>' |formal2 ='' )/递归判断A, B是否为合式公式check(Astring);check(Bstring);elseprintf("字符串% s中连接符不对ntttNO!tt 该字符串不是合式公式 n" ,formal);return ;elseif (aindex != bindex - 2)ntttNO!ttntttNO!ttif (max1 != 1 && max2 !=1 )printf("字符串% $中(A*B)不对该字符串不是合式公式 n" ,formal);return ;if ( formalaindex + 1 ='*'|formalaindex +