题解 P1241 【括号序列】
Mars_Dingdang
2020-10-01 21:35:07
写在前面：本题描述大雾，有许多细枝末节的情况没有解释。
## 题目大意
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果 $\rm S$ 是规则序列，那么 `(S)` 和 `[S]` 也是规则序列；
3．如果 $\rm A$ 和 $\rm B$ 都是规则序列，那么 $\rm A\rm B$ 也是规则序列。
现在，给你一些由 `(`，`)`，`[`，`]` 构成的序列，你要做的，是补全该括号序列，即扫描一遍原序列，对每一个右括号，找到在它左边最靠近它的左括号匹配，如果没有就放弃。在以这种方式把原序列匹配完成后，把剩下的未匹配的括号补全。
【举例说明】
- 以下属于规则序列：`()`, `()[]()`, `([])[()]`, `[(()[])]`；
- 以下不属于规则序列：`)(`, `([)]`。
## 大体思路
本题在理解题面的基础上就容易了许多，即：
- 对于每一个 `)`，都要在出现未被匹配过的 `[` 或 `]` 之前成功匹配上 `(`；
- 同理，对于每一个 `]`，都要在出现未被匹配过的 `(` 或 `)` 之前成功匹配上 `[`。
一旦在匹配某种括号的过程中遇到**另一种未被匹配过**的括号，即表明本次匹配中止，跳出循环。而对于某种括号存在剩余的情况，即视为未匹配成功。
因此，我们需要将括号序列输入至一个字符串中，然后进行遍历，遇到右括号则按上述规则倒序遍历前半部分进行匹配。在此过程中，需要一个 bool 类型的**标记数组**记录每个括号是否已被匹配。代码如下：
```cpp
for(int i=0;i<len;i++){//正序遍历字符串
if (s[i]==')'){//遇到右括号
for(int j=i-1;j>=0;j--){//倒序遍历
if (s[j]=='(' && a[j]==0){
a[i]=a[j]=1;//标记
break;
}
else if(s[j]=='[' && a[j]==0) break;//不符合规则
}
}
else if(s[i]==']'){//同理
for(int j=i-1;j>=0;j--) {
if (s[j]=='[' && a[j]==0) {
a[i]=a[j]=1;
break;
}
else if(s[j]=='(' && a[j]==0) break;
}
}
}
```
最后就是临门一脚：输出匹配后的序列。分类考虑：对于已经匹配完成的括号（即标记数组为 1），直接输出，否则圆括号输出 `()`，方括号输出 `[]`。代码如下：
```cpp
for(int i=0;i<len;i++){
if(a[i]==0){//未匹配成功
if (s[i]=='(' || s[i]==')') cout<<"()";//匹配圆括号
else cout<<"[]";
}
else cout<<s[i];//方括号
}
```
## 后记
其实刚拿到本题，以为是一个简单的括号匹配，用几个 `stack` 就可以解：
```cpp
stack<char> s1;
for(1..n)
if(s[i]=='(') s1.push('(');
else if(s[i]==')') {
if(s1.empty()) puts("No"),return 0;
else s1.pop();
}
if(!s1.empty()) puts("N0"),return 0;
puts("Yes");
```