题解 P1241 【括号序列】

这道题匹配的方式是真的没有讲清楚 看了几遍题目一脸懵 ~~甚至看了题解也还是一脸懵~~ 那这里我还是想把题意讲的更简单理解一点 原题目：扫描一遍原序列，对每一个右括号，找到在它左边最靠近它的左括号匹配，如果没有就放弃。 翻译：扫描一遍原序列，当找到一个右括号（即找到一个 ' ) ' 或者 ' ] ' 时），以它为起点向左找，找到一个**没被标记成功匹配**的左括号（即找到一个 ' ( ' 或者 ' \[ ' ），如果两者匹配的话，标记它们成功 ~~牵手~~ 匹配，如果不匹配，或者找不到左括号的话，不做任何标记。 原题目：在以这种方式把原序列匹配完成后，把剩下的未匹配的括号补全。 翻译：上面扫描一遍标记完成功匹配的括号之后，扫描一遍序列，对于标记过的括号，则直接输出；对于没有标记的括号，则补全成对输出 举例：如果有个 ' \[ ' 或 ' ] ' 没被标记匹配，则输出 \[ ] 如果还不理解的话，给个测试样例： 输入：( \[ ) ] ) 输出：( \[ ( ) ] ) ```cpp #include <iostream> #include <algorithm> #include <string> using namespace std; int a[105]; // 标记 int main() { int i,j; string s; cin >> s; for (i=0; i<s.length(); i++) { if (s[i] == ')') { // 找到了右括号 for (j=i-1; j>=0; j--) { if (s[j] == '(' and a[j] == 0) { // 找到了没被匹配过的左括号且匹配成功 a[i] = a[j] = 1; break; } else if (s[j] == '[' and a[j] == 0) break; // 找到了左括号但匹配失败 } // 找不到左括号，不做任何操作 } // 下面同理 else if (s[i] == ']') { for (j=i-1; j>=0; j--) { if (s[j] == '[' and a[j] == 0) { a[i] = a[j] = 1; break; } else if (s[j] == '(' and a[j] == 0) break; } } } for (i=0; i<s.length(); i++) { if (a[i] == 0) { // 没有匹配则成对输出 if (s[i] == '(' or s[i] == ')') cout << "()"; else cout << "[]"; } else cout << s[i]; // 匹配成功则直接输出 } return 0; } ``` 本题作为一道绿题，难度全在语文理解上 如果去除题意不明干扰的话，只能是普及-