ZZUOJ-10434: good string

Description

给定一个字符串，判断它是否是good string。

good string定义为：

① 字符s是good string，字符p是good string，字符y也是good string

② P和Q都是good string，则PQ是good string

③ P是good string，则(P)是good string

④ P是good string，则!P是good string

⑤ P和Q都是good string，则P|Q和P&Q是good string

Input

输入包含多组数据。每组数据为一行一个字符串，长度不超过100。

Output

对于每组数据，如果P是good string则输出”P is a good string”，否则输出”P is not a good string”。

Sample Input

!spy

!(s|p!y)

)sp|y

Sample Output

!spy is a good string

!(s|p!y) is a good string

)sp|y is not a good string

郑州大学第九届ACM大学生程序设计竞赛题目。

/*
 * 分类：区间DP
 * dp[i][j]表示i到j之间的那个字符串是否为good string
 * 我们所求答案即为dp[1][len]
 * dp转移方程见下列代码
 *
 *  Name: 10434: good string
 *  Copyright: __X
 *  Author: long_long_ago
 *  Date: 18/12/15 08:25
 *  Description: http://acm.zzu.edu.cn:8000/problem.php?id=10434
 *  
 */

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 105

using namespace std;
int dp[N][N];
char str[N];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif
    int i, j, k, l, len, s, e;
    bool flag;
    while(~scanf("%s", str+))
    {
        flag = false;
        len = strlen(str+);
        for (i = ; i <= len; i++)
        {
            if (str[i] == 's' || str[i] == 'p' || str[i] == 'y' || str[i] == '|' || str[i] == '&'
                || str[i] == '(' || str[i] == ')' || str[i] == '!')
            {
                continue;
            }
            else
            {
                cout << str+ << " is not a good string" << endl;
                flag = true;
                break;
            }
        }
        if (flag)   continue;
        memset(dp, , sizeof(dp));
        for (i = ; i <= len; i++)
        {
            if (str[i] == 's' || str[i] == 'p' || str[i] == 'y')    dp[i][i] = ;
        }
        for (l = ; l <= len; l++)
        {
            for (s = ; s <= len - l + ; s++)
            {
                e = s + l - ;
                if (e-s >=  && str[s] == '(' && str[e] == ')' && dp[s+][e-])
                {
                    dp[s][e] = ;
                    continue;
                }
                if (str[s] == '!' && dp[s+][e])
                {
                    dp[s][e] = ;
                    continue;
                }
                for(j = s + ; j < e; j++)
                {
                    if (dp[s][j-] && dp[j+][e])
                    {
                        if (str[j] == '|' || str[j] == '&')
                        {
                            dp[s][e] = ;
                            break;
                        }
                    }
                }
                for(k = s; k < e; k++)
                {
                    if (dp[s][k] &&dp[k+][e])
                    {
                        dp[s][e] = ;
                        break;
                    }
                } 
            }
        }
        if(dp[][len])
            printf("%s is a good string\n", str + );
        else printf("%s is not a good string\n", str + );
    }
    return ;
}

           

下面是某大神的写法 (╯▽╰)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
typedef long long LL;
const int N =  + ;
char s[N];

char f[] = "spy!|&()";
int sc(char x)
{
    for(int i = ; i < ; i ++)
        if(x == f[i])
            return ;
    return ;
}

int check()
{
    stack<char> kh;
    while(!kh.empty())kh.pop();
    for(int i = ; s[i]; i ++)
    {
        if(!sc(s[i]))
            return ;
        if(s[i] == '(')
            kh.push('(');
        else if(s[i] == ')')
        {
            if(kh.empty())
                return ;
            else
                kh.pop();
            if(s[i-] == '|' || s[i-] == '&' || s[i-] == '(' || s[i-] == '!')
                return ;
        }
        else if(s[i] == '|' || s[i] == '&')
            if(i <  || s[i-] == '|' || s[i-] == '&' || s[i-] == '!' || s[i-] == '(')
                return ;
    }

    int len = strlen(s);
    if(s[len-] == '|' || s[len-] == '&' || s[len-] == '!')
        return ;

    return kh.empty();
}

int main()
{
    while(gets(s))
        printf("%s %s\n", s, check() ? "is a good string" : "is not a good string");
    return ;
}