1、合式公式的判定1、 基本概念1、合式公式： (1)單個(gè)命題常項(xiàng)或變項(xiàng)是合式公式；(2)如果A是合式公式，則A也是合式公式；(3)如果A，B是合式公式，則PQ、PQ、PQ、 PQ也是合式公式； (4)只有有限次地應(yīng)用(1)(3)所包含的命題變?cè)?lián)結(jié)詞和括號(hào)的符號(hào)串是 合式公式。2、設(shè)命題集合Lp:C1,C2,Cn 長(zhǎng)度：語(yǔ)言構(gòu)成元素的數(shù)目 表達(dá)式u=v:指長(zhǎng)度相等且從左向右比處處相等 初始段：從最左端開(kāi)始向右掃描 結(jié)尾段：從最右端開(kāi)始向左掃描2、 編程思路假定 給定的程序變量為U ，U為L(zhǎng)p 表達(dá)式，代表輸入的帶判定的字符串又記“*”代表“”，“”，“”，“”四種之一。則：1、空表達(dá)式不是合適

2、公式的表達(dá)式。返回NO2、單獨(dú)的一個(gè)符號(hào)是一個(gè)公式時(shí)，當(dāng)且僅當(dāng)此符號(hào)為命題符號(hào)3、如果U的長(zhǎng)度大于1，則U 必須以“（”開(kāi)頭，否則不是合式公式，返回NO。（1）如果U的第二個(gè)符號(hào)為一個(gè)表示否定的“” ，則U必須是可以匹配（V） 模式， 其中V是一個(gè)表達(dá)式。否則U不是合式公式，即U是合式公式當(dāng)且僅當(dāng)V是合式公式。 于是，遞歸判斷V是否為合式公式，轉(zhuǎn)入1、重頭開(kāi)始判斷。（2）如果U的第二個(gè)符號(hào)不是“”。則U一定要符合（A*B）模式。 對(duì)U從左向右掃描，遇到“（A”停止，其中A是一個(gè)含有相同數(shù)目的“（”和“）” 的表達(dá)式，如果沒(méi)有，則U不是合式公式，返回NO。 對(duì)U從右向左掃描，遇到“B）”停止，其

3、中B是一個(gè)含有相同數(shù)目“（”和“）”的 表達(dá)式，如果沒(méi)有，則U不是合式公式，返回NO。 驗(yàn)證（A*B）的“*”是否是“”，“”，“”，“”四種之一，如果不是，則U 不是合式公式，返回NO。 遞歸判斷A，B是否為合式公式，轉(zhuǎn)入1、重頭開(kāi)始判斷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 ;/ 友好界面，循環(huán)使

4、用判斷 while( index != 0 ) printf("歡迎使用合式公式判斷系統(tǒng)n");printf("合式公式（）不可以省略n");printf("用- 表示非n");printf("用* 表示與n");printf("用+ 表示或n");printf("用> 表示蘊(yùn)涵n");printf("用 表示等值n");printf("請(qǐng)輸入您要判斷識(shí)別的字符串：n"); scanf("%s",&st

5、ring); check(string); printf("請(qǐng)選擇：0-退出系統(tǒng)；1-繼續(xù)判斷其它字符串n"); scanf( "%d", &keyNum ) ;if(keyNum = 0)break;elsecontinue; / 合式公式字符串的判讀void check(char *str1)char formal50;int len = 0;/ 獲取字符串的長(zhǎng)度并且去除空格while( *str1 != '0')if(*str1 != ' ')formallen = *str1;len+;str1+;form

6、allen = '0'printf("字符串%st有效長(zhǎng)度:%dn",formal,len);/ 空字符串不是合式公式if(len = 0)printf("字符串為空ntttNO!tt該字符串不是合式公式n");return;/ 單獨(dú)的一個(gè)符號(hào)是一個(gè)公式時(shí)，當(dāng)且僅當(dāng)次符號(hào)為命題符號(hào)else if(len = 1)if(!isalpha(formal0)printf("字符串%s不是合適字母ntttNO!tt該字符串不是合式公式n",formal);return;elseprintf("tttYES!tt字符串

7、%s 是合式公式n",formal);return;/ 如果U的長(zhǎng)度大于，則U 必須以“（”開(kāi)頭，否則不是合式公式，返回NO。elseif( (formal0 != '(') | (formallen-1 != ')')printf("字符串%s 沒(méi)有以“(”開(kāi)始或者以“)”結(jié)束ntttNO!tt該字符串不是合式公式n",formal);return;else/ 如果U的第二個(gè)符號(hào)為一個(gè)表示否定的“”，則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的第二個(gè)符號(hào)不是“”。則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 ;/ 對(duì)U從左向右掃描，遇到“（A”停止，其中A是一個(gè)含

9、有相同數(shù)目的“（”和“）”的表達(dá)式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+;/ 如果沒(méi)有，則U不是合式公式，返回NO。if(prenum != 1)printf("字符串%s 中沒(méi)有掃描到（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'/ 對(duì)U從右向左掃描，遇到“B）”停止，其中B是一個(gè)含有相同數(shù)目“（”和“）”的表達(dá)式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+;/ 如果沒(méi)有，則U不是合式公式，返回NO。if(rearnum != 1 )printf("字符串%s 中沒(méi)有掃描到 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'/ 驗(yàn)證（A*B）的“*”是否是“”，“”，“”，“”四種之一if(max1 = 1 && max2 = 1)if( formal2 = '*' | formal2 = '+' | formal2 = '>' | formal2 = '' )/ 遞歸判斷A，B是否為合式公式check(Astring); check(Bstring);elseprintf("字符串% s中連接符不對(duì)ntttNO!tt該字符串不是合式公式n",formal);return;elseif(aindex != bindex - 2)if(max1 != 1 && max2 !=1 )printf("字符串% s中（A*B）不對(duì)ntttNO!tt該字符串不是合式公式n",formal);return;if( formalaindex + 1 = '*' | formalaindex + 1 = '+' | formalai