Party解题报告
题目大意
给定若干个含有()[]和小写英文字母的字符串，问字符串是否是括号配对的。
题意
题目描述中使用了递归定义法，考虑到大家还没有学习递归，在此简单解释：
只含有英文字母的串S是正确的
这一条可以称为递归的“基本情况”，描述了最“基本”的串。
如果A, B是正确的，那么AB也是正确的。
第二条描述了两个正确的串连接后还是正确的。
如果A是正确的，那么(A)和[B]都是正确的。
第三条描述了正确的字符串可以被一对配对的括号包括，仍是正确的。
(在题目中没有写出这一条，但根据上下文是显然的) 其他串都不是正确的。
这一条称为“闭包条款”，严格的表述应该为：正确的字符串集合 C 是所有符合以上三条性质所生成的集合的交集。这条性质最小化了生成的集合。
通俗地说，这种递归定义严格化了“括号配对”的概念。同时也方便我们进行证明。
30分做法
考虑到对于30%的数据，仅出现一种括号，不难证明，仅有一种括号时，括号配对当且仅当左右括号数目相同。只需简单枚举即可得出结果。
递归分析法
这种思路即是直接使用定义进行判断，鉴于大家还没有学习递归，在此略去。有兴趣的同学可以查阅关于“语义分析”的递归下降分析法的资料。
100分做法：栈
首先仍然考虑只有一种括号的情景。为了方便处理，删去所有英文字符。考虑这样一种方法：
- 存在一个桶，对于任何字符串S，将S的第一个字符装入桶的顶端，并删去字符串中第一个字符；
- 对于桶顶第一个元素a和第二个元素b，如果b为左括号、a为右括号且ab配对，则从桶中删除这两个括号。
- 重复操作直到字符串为空。
这种思路有些诡异，如果难以理解，可以尝试使用下面的思路证明：
定理：仅存在一种括号时，最后桶为空当且仅当字符串是正确的。
部分证明：（可以略去）
1. 先证 “
- 如果原字符串为空这显然正确。
- 对字符串S的长度进行数学归纳。如果原串不空，则设原串长为
|S| 。归纳假设∀0≤|S′|<|S|,桶为空⇒字符串S′正确 。由于|S|>0 ，且串的长度减少能且仅能通过成对地删除括号完成，因而删除的括号必然是成对的。考虑最后一对删除的括号，由于算法流程，删去括号当且仅当他们相邻，所以原串中在他们之间的元素根据此算法变为了空，由于归纳假设，他们之间的串是正确的；再根据定义3，这个括号以及其间的字符串是正确的。由于是“最后一对删除的括号”，这个括号和之间的字符串（称为P）不被S种任何括号包含，因而字符串S可以看成P和另一个使桶为空的字符串A连接而成（A∩B=ϕ ），由于|A|<|S| ，根据归纳假设，A正确。由于A，P正确，根据定义2，S=AP 正确。根据归纳原理，原命题得证。
必要性证明留做练习。
用同样的方法不难证明，对于两种括号乃至n种括号，这样的方法总是正确的。 证明留作练习。
这种处理问题的“桶”称为栈，将在以后的学习中详细介绍这种结构。
标程
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char str[300];
char stk[300];
int m;
int main()
{
freopen("party.in", "r", stdin);
freopen("party.out", "w", stdout);
scanf("%d
", &m);
for (int i = 1; i <= m; i++) {
gets(str); int top = 0, j, len;
for (top = 0, j = 0, len = strlen(str); j < len; j++) {
switch(str[j]) {
case '(': stk[++top] = str[j]; break;
case ')': if (stk[top] == '(') top--; else stk[++top] = str[j]; break;
case '[': stk[++top] = str[j]; break;
case ']': if (stk[top] == '[') top--; else stk[++top] = str[j]; break;
}
}
if (top == 0) puts("Exciting");
else puts("Everything must follow the BASIC LAW");
}
return 0;
}