【题目描述】

题目链接 在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$“标注,不能匹配的右括号用”?"标注。

【输入】

((ABCD(x)

)(rttyy())sss)(

输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。

【输出】

((ABCD(x)

$$

)(rttyy())sss)(

?            ?$

分析

此题是栈的比较经典的应用，此题比较麻烦的地方在于，需要知道哪个位置的括号未匹配；所以我们栈里面存放的不能是括号了，不然不知道他是哪个位置的了； c++栈的用法 栈s里存放的是没有匹配的左括号的索引，字母、右括号索引不进栈；数组a用来标记某个索引的括号未匹配情况 栈只有两种情况，要么为空，要么有未知个数的左括号的索引； 读取字符串str每个字符 5.1读到的是左括号，直接索引进栈 5.2读到的是右括号，判断栈是否为空，如果栈空，那么此右括号就一定匹配不到，用数组a标记这个索引处的值为2；如果栈不空，那么说明栈里一定有左括号，让这个左括号出栈，说明其匹配到了 然后遍历栈的剩下元素，即没有匹配的左括号索引，用数组a在其索引位置标记为1； 最后遍历数组输出没有匹配的符号

Limitation

1s, 1024KiB for each test case.