C语言实现合式公式的判断示例
短信预约 -IT技能 免费直播动态提醒
前言
本文介绍通过
编程实现《离散数学》中的合式公式的判断。
合式公式
很明显用递归去模拟实现判断过程相对容易。（当然利用栈，循环实现也行，毕竟递归是发生在栈区（函数栈帧），另外递归解决时要处理的细节就很多了，循环会更麻烦）。
由合式公式的定义，很明显
原子公式就是我们递归的出口，确定了出口，剩下就是怎么通过递归算法，递推到这个出口
约定
| 联结词 | 代替 | |
|---|---|---|
| 非 | ！ | |
| 合取（^） | *(数量积) | |
| 析取（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语言 合式公式内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
