使用Python的棧實(shí)現(xiàn)括號匹配算法

利用Python列表實(shí)現(xiàn)一個(gè)棧的結(jié)構(gòu)，再使用棧實(shí)現(xiàn)括號匹配的算法，所謂的括號匹配是指在編程語言中，括號是成對出現(xiàn)的，最先出現(xiàn)的左括號，對應(yīng)于最后的右括號，后出現(xiàn)的左括號對應(yīng)于最新右括號，符合棧的特征

寫一個(gè)棧的類：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)

實(shí)現(xiàn)括號匹配的算法程序：

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)))"))

輸出結(jié)果：
True
再測試

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

輸出結(jié)果False

擴(kuò)展

能夠匹配多種括號，{},[]
只需要小小的改動代碼：

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}))]"))