数据结构之栈与括号匹配问题

栈（Stack）是一个数据集合，可以理解为只能在一端进行插入或者删除的列表，栈的特点是先进后出LIFO（last-in, first-out），本文用Python的列表，来实现一个栈结构。

栈的概念：栈顶、栈底

基本操作：进栈（压栈）：push、出栈：pop、取栈顶：gettop

栈结构

当然，不定义类，只使用列表的push和pop方法也可以。

class Stack():
    def __init__(self):
        self.data = []

    def push(self, elem):
        self.data.append(elem)

    def pop(self):
        return self.data.pop()

    def gettop(self):
        if len(self.data) > 0:
            return self.data[-1]
        else:
            return None


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) #3
print(stack.gettop()) #2

栈的运用：括号匹配问题

给定一个字符串，其中包括小括号、中括号、大括号，判断该字符串中的括号是否匹配。

例如：

()[]{}、([{}])  匹配

[](、([)]  不匹配

def is_match(string):
    map = {'}':'{', ']':'[', ')':'('}
    stack = Stack()
    for s in string:
        # 栈顶有值且匹配
        top = stack.gettop()
        if top and map.get(s) == top:
            stack.pop()
        else:
            stack.push(s)
    # 最后栈内没有元素
    if not stack.gettop():
        return True

string = '[]('
print(is_match(string))