C語言實現合式公式的判斷示例
前言
本文介紹通過
編程
實現《離散數學》中的合式公式的判斷。
合式公式
很明顯用遞歸去模擬實現判斷過程相對容易。(當然利用棧,循環(huán)實現也行,畢竟遞歸是發(fā)生在棧區(qū)(函數棧幀),另外遞歸解決時要處理的細節(jié)就很多了,循環(huán)會更麻煩)。
由合式公式的定義,很明顯
原子公式
就是我們遞歸的出口,確定了出口,剩下就是怎么通過遞歸算法,遞推到這個出口
約定
聯結詞 | 代替 | |
---|---|---|
非 | ! | |
合?。╚) | *(數量積) | |
析?。╒) | +(數量和) | |
蘊含(->) | > | |
等價 | = |
思路
刪除否定聯結詞
思路用一個輔助數組去占時存儲非!的字符,之后拷貝到原區(qū)間,不過要對原區(qū)間進行賦值\0
void Del_Negation(char* str,int n) { assert(str); char* tmp = (char*)calloc(n+1, sizeof(char));//多一個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那塊內存重新賦值為\0,防止tmp拷貝到str中后,s扔有舊的數據 strcpy(str, tmp); free(tmp); tmp = NULL; }
刪除括號
刪除括號,因為是對首尾進行的刪除,這里通過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); }
第一個聯結詞的下標
找尋區(qū)間中第一雙目運算符:找到就返回下標,否則就返回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] != '(')//第一個字符是字母: A>(B) { int keyi = Find_Fist_operator(str, left, right);//找尋第一個雙目運算符 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//第一個是(:(A)<B { int brackt = 0;//當brackt為0,說明將雙目運算符的左操作數全體找到了 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; //思路用一個輔助數組去占時存儲非!的字符,之后拷貝到原區(qū)間,不過要對原區(qū)間進行賦值0 void Del_Negation(char* str,int n) { assert(str); char* tmp = (char*)calloc(n+1, sizeof(char));//多一個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那塊內存重新賦值為\0,防止tmp拷貝到str中后,s扔有舊的數據 strcpy(str, tmp); free(tmp); tmp = NULL; } //刪除括號,因為是對首尾進行的刪除,這里通過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); } //判斷是否為原子式 //因為去除括號的原因,當只有一個字母是原子式,否則不是 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ū)間中第一雙目運算符:找到就返回下標,否則就返回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] != '(')//第一個字符是字母: A>(B) { int keyi = Find_Fist_operator(str, left, right);//找尋第一個雙目運算符 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//第一個是(:(A)<B { int brackt = 0;//當brackt為0,說明將雙目運算符的左操作數全體找到了 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é)的遞歸函數,只能一個一個處理調理,不能急。
到此這篇關于C語言實現合式公式的判斷示例的文章就介紹到這了,更多相關C語言 合式公式內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
C++中sprintf使用的方法與printf的區(qū)別分析
這篇文章主要介紹了C++中sprintf使用的方法與printf的區(qū)別,實例分析了sprintf與printf的具體用法及相關注意事項,具有一定參考借鑒價值,需要的朋友可以參考下2015-01-01