題目:
時間限制: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*