hihoCoder之正则表达式

题目：

时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个字符串，判断其是否为合法的正则表达式。
一个正则表达式定义为：
1：0是正则表达式，1也是正则表达式。
2：P和Q都是正则表达式，则PQ是正则表达式。
3：P是正则表达式，则(P)是正则表达式
4：P是正则表达式，则P*也是正则表达式
5：P和Q都是正则表达式，则P|Q是正则表达式。
输入
输入包含多组数据。
每组数据为一行一个字符串，长度不超过100。
输出
对于每组数据，如果输入是合法的正则表达式，输出yes，否则输出no。
样例输入
010101101*
(11|0*)*
)*111
样例输出
yes
yes
no

解法：

#include<iostream>
#include<string>
using namespace std;


string exp;

int judge(int beg,int end)
{
	int cnt=0;
	if(beg>=end)
		return 1;
	if(exp[beg]=='*'||exp[beg]=='|'||exp[end-1]=='|')
		return 0;
	for(int pos=beg;pos<=end;++pos)
	{
		if(cnt<0||(pos==end&&cnt>0))
			return 0;
		else if(pos==end&&cnt==0)
			return 1;
		if(exp[pos]=='(')
		{
			if(pos!=beg&&cnt==0)
			{
				return judge(beg,pos)&&judge(pos,end);
			}
			++cnt;
		}
		else if(exp[pos]==')')
		{
			--cnt;
			if(cnt==0)
			{
				int p=pos++;
				while(pos<end&&exp[pos]=='*')
					++pos;
				if(pos<end&&exp[pos]=='|')
				{
					return judge(beg+1,p)&&judge(pos+1,end);
				}
				return judge(beg+1,p)&&judge(pos,end);
			}
		}
		else if(exp[pos]=='|')
		{
			if(cnt==0)
			{
				return judge(beg,pos)&&judge(pos+1,end);
			}
		}
		else if(exp[pos]=='0'||exp[pos]=='1'||exp[pos]=='*');
		else return 0;
	}
	return 1;
}

int main()
{
	while(cin>>exp)
		cout<<(judge(0,exp.length())?"yes":"no")<<endl;
	return 0;
}

我的测试数据是：

(1(101)0*|(1011))

(0|(00|0)*0|0)0*

(0|(00|0)*000)0*

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!