博客

Tips：这是一个关于上一篇文章的补充，具体内容可以查看上一篇文章

思路

为了判断带有括号的情况，我的想法是把被括号括起来的字符串单独拿出来，去掉括号后作为



E

E






E





重新判断

(因为括号内的内容可能是一个完整的表达式)

代码

#include<string>
#include<iostream>

using namespace std;

bool ThisE(string E);	//提前声明


int find_rbrac(string B)	//找到右括号的位置
{
	int flag = 0;
	for (int i = 1; i < B.length(); i++)
	{
		if (B[i] == '(')
			flag++;
		if (B[i] == ')')
			if (flag == 0)
				return i;
			else
				flag--;
	}
	return 0;
}

bool is_brackets(string S)	//括号内的内容重新作为表达式E来判断
{
	int pos = find_rbrac(S);
	if (pos != 0)
	{
		if (S[pos + 1] == '+' || S[pos + 1] == '*')
		{
			string subs3 = S.substr(1, pos - 1);
			string subs4 = S.substr(pos + 2, S.length() - pos - 2);
			return ThisE(subs3) && ThisE(subs4);
		}
		else if (pos + 1 == S.length())
		{
			string subs5 = S.substr(1, pos - 1);
			return ThisE(subs5);
		}
	}
	return false;
}

int findposadd(string S)	//找到加号第一次出现的位置
{
	for (int i = 0; i < S.length(); i++)
	{
		if (S[i] == '+')
			return i;
	}
	return 0;
}

int findposmul(string S)	//找到乘号第一次出现的位置
{
	for (int i = 0; i < S.length(); i++)
	{
		if (S[i] == '*')
			return i;
	}
	return 0;
}

bool ThisF(string F)	//判断字符串F是否满足条件
{
	if (F.length() == 1 && (F[0] == 'a' || F[0] == 'b' || F[0] == 'c'))
		return true;
	else
		return false;
}

bool ThisT(string T)	//判断字符串T
{
	if (T[0] == '(')
		return is_brackets(T);
	int pos = findposmul(T);
	if (pos == 0)	//若没有乘号，则直接认为T = F
		return ThisF(T);
	string subs1 = T.substr(0, pos);	//从第一个乘号把T分成两部分 T = F + T；
	string subs2 = T.substr(pos + 1, T.length() - pos - 1);
	return ThisF(subs1) && ThisT(subs2);
}

bool ThisE(string E)	//判断字符串E
{
	if (E[0] == '(')
		return is_brackets(E);
	int pos = findposadd(E);
	if (pos == 0)	//若没有加号，则直接认为E = T
		return ThisT(E);
	string subs1 = E.substr(0, pos);	//从第一个加号把E分成两部分 E = T + E
	string subs2 = E.substr(pos + 1, E.length() - pos - 1);
	return ThisT(subs1) && ThisE(subs2);
}

void test01()
{
	string M = "(a*b)";
	cout << M.substr(1,M.length()-2) << endl;
}

int main()
{
//	test01();
	string E = "(a*(b*c))*a+b+(a+b)";
	if (ThisE(E))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	system("pause");
	return 0;
}