题目1 : 正则表达式
时间限制:
1000ms
单点时限:
1000ms
内存限制:
256MB
用栈去判断()，剩余的暴力判断
如果(xx)成立，就令(xx)=11..11 视为1个表达式。
注意以下数据
() no
0|，0||，0||1，0|* no
)( no
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (1000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; char s[MAXN]; int n,st[MAXN],tail; bool check2(int a,int b) { bool now=0; Fork(j,a+1,b-1) { if (s[j]=='0') now=1; else if (s[j]=='*') { if (now==0) return 0; } else if (s[j]=='|') { if (now==0) return 0; now=0; } } if (s[b-1]=='|') return 0; Fork(j,a,b) s[j]='0'; return 1; } bool check3(int a,b) { if (s[j]=='0') now=1; else if (s[j]=='*') { if (now==0) return 0; } else if (s[j]=='|') { if (now==0) return 0; now=0; } } if (s[b]=='|') return 0; return 1; } bool check() { tail=0; Rep(i,n) if(s[i]=='1'||s[i]=='0') s[i]='0'; else if (s[i]!='('&&s[i]!=')'&&s[i]!='*'&&s[i]!='|') return 0; Rep(i,n) { if (s[i]=='(') st[++tail]=i; else if (s[i]==')') { if (!tail) return 0; int a=st[tail--],b=i; if (a+1==b) return 0; if (!check2(a,b)) return 0; } } if (tail) return 0; if (!check3(0,n-1)) return 0; return 1; } int main() { // freopen("regular.in","r",stdin); while(scanf("%s",s)==1) { n=strlen(s); if (n==0) break; if (check()) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
