括号匹配

括号匹配就是判断一个字符串中括号是否配对如 “((()))”，“(({([])}))”等等这样就是匹配的。而“())”，“{[}]”这样就不是匹配的。也就是必须成对出现，且没有交叉。
那么怎么解决这个问题呢？一个想法就是分别计算各自左右括号的数量，分别对比是否相等。但这样会将括号交叉时的情况误判为正常匹配。
进一步观察可以发现，右括号一定是和距离它最近的左括号是一对，否则就是括号交叉了，必定不匹配（比如[{]}）。因此，当遇到右括号时，就向回查看，离他最近的一个左括号是否和他属于统一类型的括号，直到遍历完所有括号。
因为需要向回查看，所以可以用栈来试试。Python中没有栈数据类型，需要先手动实现栈。

class Stack(object):
	def __init__(self):
		self.lt = []
	
	def push(self, item):
		self.lt.append(item)
	
	def pop(self):
		return self.lt.pop()
	
	def peek(self):
		if len(self.lt) == 0:
			return ''
		else:
			return self.lt[-1]
	def size(self):
		return len(self.lt)
	
	def isEmpty(self):
		return self.lt == []1234567891011121314151617181920

定义好stack类之后，再来看括号匹配的问题。遍历给定的字符串，如果遇到左括号，就把它入栈，如果遇到右括号，就查看栈顶，此时栈内全是左括号，因此栈顶就是距离该右括号最近的左括号，查看是否属于一对，如果是则弹栈，继续遍历，重复上述动作，如果不是则不匹配。
那怎么判断是否属于一对呢？这里针对左右括号，分别定义两个列表，计算其下标即可。

def matches(left, right):
    l = '([{'
    r = ')]}'
    if l.index(left) == r.index(right):
        return True
    else:
        return False1234567

def parCheckers(symbolString):

    s = Stack()
    for i in symbolString:
    	# 左括号，入栈
        if i in '([{':
            s.push(i)
        else:
        	# 如果栈已空，则说明右括号多，不批匹配
            if s.isEmpty():
                break
            else:
            	# 否则判断是否是一对
                let = s.pop()
                if not matches(let, i):
                    break
                
    else:
    	# 已经遍历完，如果栈未空，说明左括号多，不匹配
        if s.isEmpty():
            return True
        else:
            return False
    return False

作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/108034314

来源：CSDN
著作权归作者所有，转载请联系作者获得授权，切勿私自转载。