C語言實(shí)現(xiàn)合式公式的判斷示例
前言
本文介紹通過
編程
實(shí)現(xiàn)《離散數(shù)學(xué)》中的合式公式的判斷。
合式公式
很明顯用遞歸去模擬實(shí)現(xiàn)判斷過程相對容易。(當(dāng)然利用棧,循環(huán)實(shí)現(xiàn)也行,畢竟遞歸是發(fā)生在棧區(qū)(函數(shù)棧幀),另外遞歸解決時(shí)要處理的細(xì)節(jié)就很多了,循環(huán)會(huì)更麻煩)。
由合式公式的定義,很明顯
原子公式
就是我們遞歸的出口,確定了出口,剩下就是怎么通過遞歸算法,遞推到這個(gè)出口
約定
聯(lián)結(jié)詞 | 代替 | |
---|---|---|
非 | ! | |
合?。╚) | *(數(shù)量積) | |
析取(V) | +(數(shù)量和) | |
蘊(yùn)含(->) | > | |
等價(jià) | = |
思路
刪除否定聯(lián)結(jié)詞
思路用一個(gè)輔助數(shù)組去占時(shí)存儲(chǔ)非!的字符,之后拷貝到原區(qū)間,不過要對原區(qū)間進(jìn)行賦值\0
void Del_Negation(char* str,int n) { assert(str); char* tmp = (char*)calloc(n+1, sizeof(char));//多一個(gè)1,是為了放置\0,避免strcpy越界拷貝 assert(tmp); int cnt = 0; int i = 0; while (i < n)//將除!的字符賦值到tmp中 { if (str[i] != '!') { tmp[cnt++] = str[i]; } ++i; } memset(str, 0, sizeof(char)*n);//對str那塊內(nèi)存重新賦值為\0,防止tmp拷貝到str中后,s扔有舊的數(shù)據(jù) strcpy(str, tmp); free(tmp); tmp = NULL; }
刪除括號
刪除括號,因?yàn)槭菍κ孜策M(jìn)行的刪除,這里通過2次strcpy就可以完成
void Del_Bracket( char* str, int left, int right) { assert(str); char* tmp = (char*)calloc(right - left +1+1, sizeof(char)); assert(tmp); str[right] = '\0'; strcpy(tmp, str+left+1); strcpy(str+left, tmp); }
第一個(gè)聯(lián)結(jié)詞的下標(biāo)
找尋區(qū)間中第一雙目運(yùn)算符:找到就返回下標(biāo),否則就返回0.
int Find_Fist_operator( char* str, int left, int right) { int ret = 0; while (left<right) { if (str[left + 1] == '+' || str[left + 1] == '*' || str[left + 1] == '>' || str[left + 1] == '=') { ret = left + 1; return ret; } ++left; } return 0;//如果ret是0,說明是非法,反之就正確 }
判斷合式公式
注意區(qū)間的操作,不然很容易造成野指針的訪問。
bool Is_CombForm(char* str, int left, int right) { if ((0 == (right - left))//區(qū)間是原子命題 && ('A' <= str[left] || 'Z' >= str[left])) { return true; } if (str[left] != '(')//第一個(gè)字符是字母: A>(B) { int keyi = Find_Fist_operator(str, left, right);//找尋第一個(gè)雙目運(yùn)算符 if (keyi > 0) { if (str[keyi + 1] == '(')//A<(B) { Del_Bracket(str, keyi + 1, right); return Is_CombForm(str, left, keyi - 1) && Is_CombForm(str, keyi + 1, right - 2); } else//A<B { return Is_CombForm(str, left, keyi - 1) && Is_CombForm(str, keyi + 1, right); } } } else//第一個(gè)是(:(A)<B { int brackt = 0;//當(dāng)brackt為0,說明將雙目運(yùn)算符的左操作數(shù)全體找到了 int cnt = left; int flag = 0; while (cnt<right) { if (str[cnt] == '(') { brackt++; } if (str[cnt] == ')') { brackt--; flag = cnt; } ++cnt; //[ left , flag] > [flag+2,right] if (brackt == 0) { Del_Bracket(str, left, flag); if (str[flag + 2] == '(') { Del_Bracket(str, flag + 2, right); return Is_CombForm(str, left, flag - 2) && Is_CombForm(str, flag+ 2, right - 2); } else { return Is_CombForm(str, left, flag - 2) && Is_CombForm(str, flag + 2, right); } } } } return false; }
所有代碼
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <stdlib.h> #include <string.h> #include <assert.h> #include<time.h> #include<windows.h> using namespace std; //思路用一個(gè)輔助數(shù)組去占時(shí)存儲(chǔ)非!的字符,之后拷貝到原區(qū)間,不過要對原區(qū)間進(jìn)行賦值0 void Del_Negation(char* str,int n) { assert(str); char* tmp = (char*)calloc(n+1, sizeof(char));//多一個(gè)1,是為了放置\0,避免strcpy越界拷貝 assert(tmp); int cnt = 0; int i = 0; while (i < n)//將除!的字符賦值到tmp中 { if (str[i] != '!') { tmp[cnt++] = str[i]; } ++i; } memset(str, 0, sizeof(char)*n);//對str那塊內(nèi)存重新賦值為\0,防止tmp拷貝到str中后,s扔有舊的數(shù)據(jù) strcpy(str, tmp); free(tmp); tmp = NULL; } //刪除括號,因?yàn)槭菍κ孜策M(jìn)行的刪除,這里通過2次strcpy就可以完成 void Del_Bracket( char* str, int left, int right) { assert(str); char* tmp = (char*)calloc(right - left +1+1, sizeof(char)); assert(tmp); str[right] = '\0'; strcpy(tmp, str+left+1); strcpy(str+left, tmp); } //判斷是否為原子式 //因?yàn)槿コㄌ柕脑?,?dāng)只有一個(gè)字母是原子式,否則不是 bool Is_operator(const char* str,int left,int right) { assert(str); if ((0==(right-left)) &&('A' <=str[left]||'Z'>=str[left])) { return true; } return false; } //找尋區(qū)間中第一雙目運(yùn)算符:找到就返回下標(biāo),否則就返回0. int Find_Fist_operator( char* str, int left, int right) { int ret = 0; while (left<right) { if (str[left + 1] == '+' || str[left + 1] == '*' || str[left + 1] == '>' || str[left + 1] == '=') { ret = left + 1; return ret; } ++left; } return 0;//如果ret是0,說明是非法,反之就正確 } bool Is_CombForm(char* str, int left, int right) { if ((0 == (right - left))//區(qū)間是原子命題 && ('A' <= str[left] || 'Z' >= str[left])) { return true; } if (str[left] != '(')//第一個(gè)字符是字母: A>(B) { int keyi = Find_Fist_operator(str, left, right);//找尋第一個(gè)雙目運(yùn)算符 if (keyi > 0) { if (str[keyi + 1] == '(')//A<(B) { Del_Bracket(str, keyi + 1, right); return Is_CombForm(str, left, keyi - 1) && Is_CombForm(str, keyi + 1, right - 2); } else//A<B { return Is_CombForm(str, left, keyi - 1) && Is_CombForm(str, keyi + 1, right); } } } else//第一個(gè)是(:(A)<B { int brackt = 0;//當(dāng)brackt為0,說明將雙目運(yùn)算符的左操作數(shù)全體找到了 int cnt = left; int flag = 0; while (cnt<right) { if (str[cnt] == '(') { brackt++; } if (str[cnt] == ')') { brackt--; flag = cnt; } ++cnt; //[ left , flag] > [flag+2,right] if (brackt == 0) { Del_Bracket(str, left, flag); if (str[flag + 2] == '(') { Del_Bracket(str, flag + 2, right); return Is_CombForm(str, left, flag - 2) && Is_CombForm(str, flag+ 2, right - 2); } else { return Is_CombForm(str, left, flag - 2) && Is_CombForm(str, flag + 2, right); } } } } return false; } void Text(char *str) { cout << str; int sz = strlen(str); Del_Negation(str, sz); sz = strlen(str); if (Is_CombForm(str, 0, sz-1)) { printf("-------YES\n"); } else { printf("----------NO\n"); } } int main () { char arr1[] = "P>!R"; char arr2[] = "!(P>Q)>!R"; char arr3[] = "P>((P*R)>Q)"; char arr4[] = "((P>R)*(Q*(P>R)))=R"; char arr5[] = "((P>Q)>R)>Y"; char arr6[] = "PQ"; char arr7[] = "(P>RT)>Q"; char arr8[] = "((P>Q)*(P>QT))>(R*T)"; Text(arr1); Text(arr2); Text(arr3); Text(arr4); Text(arr5); Text(arr6); Text(arr7); Text(arr8); printf("-------------------------BY New Young\n"); return 0; }
效果
總結(jié)
對于復(fù)雜的需要很多細(xì)節(jié)的遞歸函數(shù),只能一個(gè)一個(gè)處理調(diào)理,不能急。
到此這篇關(guān)于C語言實(shí)現(xiàn)合式公式的判斷示例的文章就介紹到這了,更多相關(guān)C語言 合式公式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++中sprintf使用的方法與printf的區(qū)別分析
這篇文章主要介紹了C++中sprintf使用的方法與printf的區(qū)別,實(shí)例分析了sprintf與printf的具體用法及相關(guān)注意事項(xiàng),具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-01-01C++深入探索內(nèi)聯(lián)函數(shù)inline與auto關(guān)鍵字的使用
本篇文章主要包括內(nèi)聯(lián)函數(shù)和auto關(guān)鍵字。其中,內(nèi)斂函數(shù)包括概念,特性等;auto關(guān)鍵字的使用規(guī)則,使用場景等,接下來讓我們深入了解2022-05-05