Problem Description
在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。
Input Description
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。 注意:cin.getline(str,100)最多只能输入99个字符!Output Description
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。
Sample Input
bge))))))))) ((IIII)))))) ()()()()(uuu ))))UUUU((()
Sample Output
bge))))))))) ????????? ((IIII)))))) ???? ()()()()(uuu $ ))))UUUU((() ???? $$
Hint
算法思想:
括号匹配是典型的栈的应用,因此可以采用链栈,思路如下: (1)第一次遍历输入字符串, 1.是左括号,则入栈,同时标记数组的相应位置置空格 2.是右括号,则检测栈是否为空,不为空,则判断有对应的左括号,同时出栈;为空,则没有对应的左括号,标记数组置‘?’ (2)第二次遍历输入字符串, 1.是右括号,则入栈。 2.是左括号,则检测栈是否为空,不为空,则判断有对应的右括号,同时出栈;为空,则没有对应的左括号,标记数组置‘$’。 ac代码:1 # 本题易错,List是可变的,传到函数里是指针,所以赋值给新的变量保存也会修改它本身的值,只能拷贝保存 2 # 找左括号无法匹配要逆转列表看入栈的顺序 3 # 顺序存储 4 class Stack(object): 5 # 初始化一个栈 6 def __init__(self, size=100): 7 self.stack = [] 8 self.size = size 9 self.top = -1 10 11 # 判断堆栈是否为空 12 def isEmpty(self): 13 return self.top == -1 14 15 # 判断栈是否已满 16 def is_full(self): 17 return self.top + 1 == self.size 18 19 # 入栈操作 20 def pushStack(self, val): 21 if self.is_full(): 22 raise Exception("Stack is full") 23 else: 24 self.top += 1 25 self.stack.append(val) 26 27 # 出栈操作 28 def popStack(self): 29 if self.isEmpty(): 30 raise Exception("Stack is empty") 31 else: 32 self.top -= 1 33 self.stack.pop() 34 35 def func(): 36 while True: 37 try: 38 x = [] 39 x = input() 40 x = list(x) 41 Match(x) 42 except EOFError: 43 break 44 def Match(line): 45 t = [] 46 t = line.copy() 47 print(''.join(t)) 48 # 实例化一个栈 49 s = Stack() 50 j = 0 51 # 找右括号是否匹配 52 for i in line: 53 t[j] = ' ' 54 if i=='(': 55 s.pushStack(i) 56 if i==')': 57 if s.isEmpty(): 58 t[j] = '?' 59 else: 60 s.popStack() 61 j += 1 62 # 找左括号是否匹配,注意不能拆开比较,括号有左右之分 63 w = Stack() 64 flag = 0 65 length = len(line) 66 j = 0 67 m = line[::-1] 68 for i in m: 69 if i == ')': 70 w.pushStack(i) 71 if i == '(': 72 if w.isEmpty(): 73 t[length-1-j] = '$' 74 else: 75 w.popStack() 76 j += 1 77 print(''.join(t)) 78 if __name__ == '__main__': 79 func()
标签:__,匹配,self,括号,Problem,line,def From: https://www.cnblogs.com/hangsingplus/p/17362986.html