1126:Simply Syntax

keyword

構文解析　C

概要

pはvalid。sがvalidなとき、Nsはvalid。s,tがvalidなとき、Cstはvalid。このルールの元で、与えられた文字列がvalidかどうかを判定する問題。
素直に実装する。あと多分メモ化は意味ないはず。

char str[300];
int memo[300][300];
int n;

int preCheck(){
    int i,j;
    for(i=0;i<n;i++){
        if('p'<=str[i]&&str[i]<='z')
            str[i] = 'p';
        else if(str[i]=='C' || str[i]=='D' || str[i]=='E' || str[i]=='I')
            str[i] = 'C';
        else if(str[i]!='N')
            return 0;
    }
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            memo[i][j] = -1;
    return 1;
}

int isCorrect(int from, int end){
    int i;
    char c=str[from];
    if(from>=end) return 0;
    if(memo[from][end]>=0) return memo[from][end];
    if(c=='p') return memo[from][end] = (end-from==1?1:0);
    else if(c=='N') return memo[from][end] = isCorrect(from+1,end);
    else{
        for(i=from+1;i<end;i++)
            if(isCorrect(from+1,i) && isCorrect(i,end))
                return memo[from][end] = 1;
    }
    return memo[from][end] = 0;
}

int main(){
    while(scanf("%s\n",str)!=EOF){
        n = strlen(str);
        puts((preCheck()&&isCorrect(0,n))?"YES":"NO");
    }
}