注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为7分钟。
括号匹配情况介绍
我们经常会遇到类似(9-1)*(8+7)/(4-2)、print("Go on!")这样含有括号的例子。在代码中，还有大量类似包含多重括号的例子，如：
l = list(map(int,input().split()))
括号的使用有其固定的规则：
首先，每个开括号必然由于与之对应的闭括号；其次，每一对开闭括号都要有正确的嵌套。
正确的括号如：
(()()()), ((())), (()(())()).
错误的括号如：
(((()), ()(()))).
现在要解决的是，如何构造括号匹配识别算法。
从左到右扫描括号串，最新打开的左括号，应该匹配最先遇到的右括号。
按这样的机制，第一个左括号（最先遇到的）应该匹配最后一个右括号（最后遇到的）。
这种次序反转，正好符合栈的特性。
只匹配"()"括号的案例
算法流程
- 假设只含有左右括号的字符串为s。
- 新建一个空栈，对s从左至右依次取括号。
- 如果是左括号，入栈。继续对s取括号。
- 如果遇到右括号，看栈是否为空，若不为空，从栈顶移除左括号；若为空，此时括号匹配出了问题，匹配失败，结束。
- 如果上述循环能持续到s取括号完毕，则最后看栈是否为空，空了就匹配成功，不空就匹配失败，结束。
代码如下：
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol == "(":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
s.pop()
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
print(parChecker('((()))'))
print(parChecker('(()'))
<<<
True
False
<<<
匹配"()[]{}"括号的案例
括号种类变多了以后，比如有“{}”、“[]”、“()”等括号，情况变复杂了。尽管如此，总的来说，需要修改的地方只有2处：
- 碰到各种左括号仍然入栈。
- 碰到各种右括号的时候需要判断栈顶的左括号是否成对。
代码如下：
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{": #修改之一。
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
#修改之二。
top = s.pop()
if not matches(top, symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
#新添加的函数。
def matches(open, close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
print(parChecker('{{([][])}()}'))
print(parChecker('[{()]'))
<<<
False
False
<<<
通用括号匹配算法可以应用于其它领域，比如HTML/XML文档也有类似于括号的开闭标记。
To be continued.
