C語(yǔ)言怎么實(shí)現(xiàn)合式公式的判斷

這篇文章主要講解了“C語(yǔ)言怎么實(shí)現(xiàn)合式公式的判斷”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“C語(yǔ)言怎么實(shí)現(xiàn)合式公式的判斷”吧！

合式公式

很明顯用遞歸去模擬實(shí)現(xiàn)判斷過(guò)程相對(duì)容易。（當(dāng)然利用棧，循環(huán)實(shí)現(xiàn)也行，畢竟遞歸是發(fā)生在棧區(qū)（函數(shù)棧幀），另外遞歸解決時(shí)要處理的細(xì)節(jié)就很多了，循環(huán)會(huì)更麻煩）。

由合式公式的定義，很明顯原子公式就是我們遞歸的出口，確定了出口，剩下就是怎么通過(guò)遞歸算法，遞推到這個(gè)出口

約定

思路

刪除否定聯(lián)結(jié)詞

思路用一個(gè)輔助數(shù)組去占時(shí)存儲(chǔ)非!的字符，之后拷貝到原區(qū)間，不過(guò)要對(duì)原區(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);//對(duì)str那塊內(nèi)存重新賦值為\0,防止tmp拷貝到str中后，s扔有舊的數(shù)據(jù)
	strcpy(str, tmp);
	free(tmp);
	tmp = NULL;
}

刪除括號(hào)

刪除括號(hào)，因?yàn)槭菍?duì)首尾進(jìn)行的刪除，這里通過(guò)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，說(shuō)明是非法，反之就正確
}

判斷合式公式

注意區(qū)間的操作，不然很容易造成野指針的訪(fǎng)問(wèn)。

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，說(shuō)明將雙目運(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ū)間，不過(guò)要對(duì)原區(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);//對(duì)str那塊內(nèi)存重新賦值為\0,防止tmp拷貝到str中后，s扔有舊的數(shù)據(jù)
	strcpy(str, tmp);
	free(tmp);
	tmp = NULL;
}

//刪除括號(hào)，因?yàn)槭菍?duì)首尾進(jìn)行的刪除，這里通過(guò)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)槿コㄌ?hào)的原因，當(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，說(shuō)明是非法，反之就正確
}

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，說(shuō)明將雙目運(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;
}

效果

感謝各位的閱讀，以上就是“C語(yǔ)言怎么實(shí)現(xiàn)合式公式的判斷”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)C語(yǔ)言怎么實(shí)現(xiàn)合式公式的判斷這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！