#3866. 括号匹配问题(C++三级)
括号匹配问题(C++三级)
【题目描述】
题目链接 在某个字符串(长度不超过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.