C語言實(shí)現(xiàn)合式公式的判斷示例
更新時(shí)間：2022年04月03日 10:08:32 作者：New Youg
這篇文章主要介紹了C語言實(shí)現(xiàn)合式公式的判斷示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
前言
本文介紹通過
編程實(shí)現(xiàn)《離散數(shù)學(xué)》中的合式公式的判斷。
合式公式
很明顯用遞歸去模擬實(shí)現(xiàn)判斷過程相對(duì)容易。（當(dāng)然利用棧，循環(huán)實(shí)現(xiàn)也行，畢竟遞歸是發(fā)生在棧區(qū)（函數(shù)棧幀），另外遞歸解決時(shí)要處理的細(xì)節(jié)就很多了，循環(huán)會(huì)更麻煩）。
由合式公式的定義，很明顯
原子公式就是我們遞歸的出口，確定了出口，剩下就是怎么通過遞歸算法，遞推到這個(gè)出口
約定
| 聯(lián)結(jié)詞 | 代替 | |
|---|---|---|
| 非 | ！ | |
| 合?。╚） | *(數(shù)量積) | |
| 析?。╒） | +（數(shù)量和） | |
| 蘊(yùn)含（->） | > | |
| 等價(jià) | = |
思路
刪除否定聯(lián)結(jié)詞
思路用一個(gè)輔助數(shù)組去占時(shí)存儲(chǔ)非!的字符，之后拷貝到原區(qū)間，不過要對(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)行的刪除，這里通過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，說明是非法，反之就正確
}
判斷合式公式
注意區(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] != '(')//第一個(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，說明將雙目運(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ū)間，不過要對(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)行的刪除，這里通過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，說明是非法，反之就正確
}
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，說明將雙目運(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;
}
效果
總結(jié)
對(duì)于復(fù)雜的需要很多細(xì)節(jié)的遞歸函數(shù)，只能一個(gè)一個(gè)處理調(diào)理，不能急。
到此這篇關(guān)于C語言實(shí)現(xiàn)合式公式的判斷示例的文章就介紹到這了,更多相關(guān)C語言 合式公式內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++ 手把手教你實(shí)現(xiàn)可變長(zhǎng)的數(shù)組實(shí)現(xiàn)
這篇文章主要介紹了C++ 手把手教你實(shí)現(xiàn)可變長(zhǎng)的數(shù)組實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
本文給大家分享的是去年制作的一個(gè)純C語言實(shí)現(xiàn)的五子棋的代碼，雖然沒有帶漂亮的界面，還是推薦給大家，有需要的小伙伴可以參考下。2015-03-03
這篇文章主要為大家詳細(xì)介紹了C++代碼實(shí)現(xiàn)逆波蘭式，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
解析VScode在Windows環(huán)境下c_cpp_properties.json文件配置問題(推薦)
這篇文章主要介紹了解析VScode在Windows環(huán)境下c_cpp_properties.json文件配置問題,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-05-05
本文主要介紹了C++?指針傳遞的作用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
C++內(nèi)核對(duì)象封裝單實(shí)例啟動(dòng)程序的類
這篇文章主要介紹了利用C++內(nèi)核對(duì)象封裝的類，程序只能運(yùn)行單個(gè)實(shí)例，可防止多次啟動(dòng)，大家參考使用吧2013-11-11
c語言實(shí)現(xiàn)二叉查找樹實(shí)例方法
這篇文章主要介紹了一個(gè)c語言版的二叉查找樹實(shí)現(xiàn)，二叉查找樹，支持的操作包括：SERACH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE，大家參考使用吧2013-11-11
C++11中為了更好的支持泛型編程，提供了?auto和decltype兩個(gè)關(guān)鍵詞,目的就是提供編譯階段的自動(dòng)類型推導(dǎo)，這篇文章主要介紹了C++11中的類型推斷,需要的朋友可以參考下2023-01-01
C++實(shí)現(xiàn)學(xué)生選課系統(tǒng)的思路與詳細(xì)過程
C語言是在國(guó)內(nèi)外廣泛使用的一種計(jì)算機(jī)語言,下面這篇文章主要給大家介紹了關(guān)于C++實(shí)現(xiàn)學(xué)生選課系統(tǒng)的思路與詳細(xì)過程,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01
C語言函數(shù)棧幀的創(chuàng)建與銷毀原理圖解
我們知道c語言中函數(shù)都是被調(diào)用的，main函數(shù)里面能調(diào)用其他函數(shù)，其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的，下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程，一起看看吧2022-05-05