溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“C語言怎么實現合式公式的判斷”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C語言怎么實現合式公式的判斷”吧！
很明顯用遞歸去模擬實現判斷過程相對容易。（當然利用棧，循環實現也行，畢竟遞歸是發生在棧區（函數棧幀），另外遞歸解決時要處理的細節就很多了，循環會更麻煩）。
由合式公式的定義，很明顯
原子公式就是我們遞歸的出口，確定了出口，剩下就是怎么通過遞歸算法，遞推到這個出口
| 聯結詞 | 代替 | |
|---|---|---|
| 非 | ！ | |
| 合取（^） | *(數量積) | |
| 析取（V） | +（數量和） | |
| 蘊含（->） | > | |
| 等價 | = |
思路用一個輔助數組去占時存儲非!的字符，之后拷貝到原區間，不過要對原區間進行賦值\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);
}找尋區間中第一雙目運算符：找到就返回下標，否則就返回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))//區間是原子命題
&& ('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;
//思路用一個輔助數組去占時存儲非!的字符，之后拷貝到原區間，不過要對原區間進行賦值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;
}
//找尋區間中第一雙目運算符：找到就返回下標，否則就返回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))//區間是原子命題
&& ('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;
}效果
感謝各位的閱讀，以上就是“C語言怎么實現合式公式的判斷”的內容了，經過本文的學習后，相信大家對C語言怎么實現合式公式的判斷這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
