C语言怎么实现合式公式的判断

这篇文章主要讲解了“C语言怎么实现合式公式的判断”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C语言怎么实现合式公式的判断”吧！

合式公式

很明显用递归去模拟实现判断过程相对容易。（当然利用栈，循环实现也行，毕竟递归是发生在栈区（函数栈帧），另外递归解决时要处理的细节就很多了，循环会更麻烦）。

由合式公式的定义，很明显原子公式就是我们递归的出口，确定了出口，剩下就是怎么通过递归算法，递推到这个出口

约定

思路

删除否定联结词

思路用一个辅助数组去占时存储非!的字符，之后拷贝到原区间，不过要对原区间进行赋值\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;//思路用一个辅助数组去占时存储非!的字符，之后拷贝到原区间，不过要对原区间进行赋值0void 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语言怎么实现合式公式的判断这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！