Skip to content

11127: 【原1127】Water Problem

题目

题目描述

author: Xutong Chen 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1127

Description

据说大主任认识一个自认为很聪明的人。

有一天,大主任问那个人:

“你能告诉我一个集合的表示法么?”

“当然,我这么聪明!”他回答说,“那是一组在两个大括号包围的元素,但括号里也可以为空。这些元素可以是一个新的集合,也可以是一个字母,他们之间用‘,’隔开。”

“那么。”大主任说,“如果我给你一个表示,你能告诉我它是一个正确的集合吗?”

“当然,我这么聪明!”他又回答说,“傻瓜都会做。”

“很好”大主任想,“这样我就可以证明他是傻瓜了!”

现在大主任准备用这样一道题来虐掉那个人。你将得到下列规定:

集合:“{” 元素列表 “}”

元素列表:空 or 元素子列表

元素子列表:元素 or 元素“,”元素子列表

元素:子元素 or 集合

子元素:“{” or “,” or“}”

注意:“空”,表示没有任何成分,并不是有一个表示“空”的字符。

大主任觉得这题太水了,他不屑于写标程,倒是给出了一大堆邪恶的数据。为了帮助大主任证明那个人是傻瓜,作为大主任下手的你也就难逃帮他写标程的厄运了。请你写一个程序判断一个表达式是否是满足上述规定的集合。

Input Format

本题有多组数据。

输入的第一行为数据组数T。

第2到T+1行,每行给出一个字符串。

Output Format

共T行。

按下列格式输出:

若是一个满足规定的集合,则输出:“Word #数据组号: Set”

若不是,则输出:“Word #数据组号: No Set”

Sample Input

4
{}
{{}}
{{}},{,}}
{,,}

Sample Output

Word #1: Set
Word #2: Set
Word #3: Set
Word #4: No Set

Hint

对于40%数据,字符串长度不超过6;

对于100%数据,字符串长度不超过200,T<=1000。

FineArtz's solution

/* Water Problem */
#include <iostream>
#include <cstring>
using namespace std;

int t;
char s[205];
int isSublist[205][205];

inline bool readSet(const char *, int, int);
inline bool readElementSublist(const char *, int, int);
inline bool readElement(const char *, int, int);
inline bool readSubelement(const char *, int, int);

inline bool readSet(const char *s, int first, int last){
    if (s[first] != '{' || s[last - 1] != '}')
        return false;
    if (last - first == 2)
        return true;
    return readElementSublist(s, first + 1, last - 1);
}

inline bool readElementSublist(const char *s, int first, int last){
    if (isSublist[first][last] == 1)
        return true;
    if (isSublist[first][last] == -1)
        return false;
    for (int i = first; i < last; ++i){
        if (s[i] != ',')
            continue;
        if (readElement(s, first, i) && readElementSublist(s, i + 1, last))
            return true;
    }
    bool flag = readElement(s, first, last);
    if (flag)
        isSublist[first][last] = 1;
    else
        isSublist[first][last] = -1;
    return flag;
}

inline bool readElement(const char *s, int first, int last){
    if (last - first == 1){
        if (s[first] == '{' || s[first] == '}' || s[first] == ',')
            return true;
        else
            return false;
    }
    return readSet(s, first, last);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; ++i){
        cin >> s;
        int len = strlen(s);
        memset(isSublist, 0, sizeof(isSublist));
        if (readSet(s, 0, len))
            cout << "Word #" << i << ": Set\n";
        else
            cout << "Word #" << i << ": No Set\n";
    }
    return 0;
}