使用Python的栈实现括号匹配算法

利用Python列表实现一个栈的结构，再使用栈实现括号匹配的算法，所谓的括号匹配是指在编程语言中，括号是成对出现的，最先出现的左括号，对应于最后的右括号，后出现的左括号对应于最新右括号，符合栈的特征

写一个栈的类：stack.py

class Stack: def __init__(self): self.items = [] def is_Empty(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(items)-1] def size(self): return len(self.items)

实现括号匹配的算法程序：

from stack import Stack def parChecker(symbolString): s = Stack() balanced = True index = 0 while index < len(symbolString) and balanced: symbol = symbolString[index] if symbol == "(": s.push(symbol) elif symbol == ")": if s.is_Empty(): balanced = False else: s.pop() index += 1 if balanced and s.is_Empty(): return True else: return False print(parChecker("(((2356)))"))

输出结果：
True
再测试

print(parChecker("(()))"))

输出结果False

扩展

能够匹配多种括号，{},[]
只需要小小的改动代码：

from stack import Stack def parChecker(symbolString): s = Stack() balanced = True index = 0 while index < len(symbolString) and balanced: symbol = symbolString[index] if symbol in "({[": s.push(symbol) elif symbol in ")}]": if s.is_Empty(): balanced = False else: s.pop() index += 1 if balanced and s.is_Empty(): return True else: return False print(parChecker("[(({fdf}))]"))