| 描述 | |
| 在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算术式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号：首先输出原来字符串，下一行是和原字符串等长的一行，标出不能匹配的括号，其中不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注 | |
| 关于输入 | |
| 第一行一个正整数n,表示数据的组数。后面n行，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100 | |
| 关于输出 | |
| 对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，与第一行等长，"$"和"?"表示与之对应的左括号和右括号不能匹配。 注意：即使所有括号都匹配，第二行也要输出等长的一行空格 | |
| 例子输入 | |
2 ((ABCD(x) )(rttyy())sss)( | |
| 例子输出 | |
((ABCD(x) $$ )(rttyy())sss)( ? ?$ |
方法：
从左开始遍历，如果遇到左括号1在位置x，则从下一位往后寻找右括号1在位置y，找到后则从右括号1前一位往前寻找左括号2，标记左括号2与右括号1位’ ‘，他们是正确匹配。如果左括号1与2为同一位置的括号，则从下一位置x+1进行下一次寻找；若左括号1与2不同，则从y+1位置开始继续寻找右括号。
若开始遇到的是右括号，情形相似。
最终标记的结果：
所有匹配的括号——空格；
所有不是括号的字符——空格；
不匹配的括号——保留，不做改动。
#include#include using namespace std; void mark(string &s)//记得加&，否则实参不会改变！ { int l = s.size(); for (int i = 0; i < l; ++i) { if (s[i] == '(') { int flag = 1; for (int j = i+1; j < l; ++j) { if (s[j] == ')') { for (int m = j - 1; m >= i; --m) { if(s[m]=='('){ s[m] = ' '; s[j] = ' '; if (m == i) { flag = 0; } break; } } } if (flag == 0) { break; } } } else if (s[i] == ')') { int flag = 1; for (int j = i - 1; j >= 0; --j) { if (s[j] == '(') { for (int m = j + 1; m <= i; ++m) { if (s[m] == ')') { s[m] = ' '; s[j] = ' '; if (m == i) { flag = 0; } break; } } } if (flag == 0) { break; } } } else s[i] = ' '; } } int main() { int N; cin >> N; while (N--) { string str; cin >> str; int len = str.size(); cout << str << endl; mark(str); for (int i = 0; i < len; ++i) { if (str[i] == '(') { cout << "$"; } else if (str[i] == ')') { cout << "?"; } else cout << " "; } cout << endl; } }
