输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。 注意:cin.getline(str,100)最多只能输入99个字符!
请先登录再刷题,不会做的题目右上可以查看题解和答案~
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。 注意:cin.getline(str,100)最多只能输入99个字符!
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。
bge))))))))) ((IIII)))))) ()()()()(uuu ))))UUUU((()
bge))))))))) ????????? ((IIII)))))) ???? ()()()()(uuu $ ))))UUUU((() ???? $$
算法思想: 括号匹配是典型的栈的应用,因此可以采用链栈,思路如下: (1)第一次遍历输入字符串, 1.是左括号,则入栈,同时标记数组的相应位置置空格 2.是右括号,则检测栈是否为空,不为空,则判断有对应的左括号,同时出栈;为空,则没有对应的左括号,标记数组置‘?’ (2)第二次遍历输入字符串, 1.是右括号,则入栈。 2.是左括号,则检测栈是否为空,不为空,则判断有对应的右括号,同时出栈;为空,则没有对应的左括号,标记数组置‘$’。
北京大学机试题