基本數據結構之括弧匹配-基於棧的實現

• 2020 年 4 月 20 日
• 筆記
• 數據結構和演算法

from stack import Stack


def parChecker1(symbolString):
    """
    # 1. 創建一個空棧，默認標記為匹配成功
    # 2. 從左到右依次取括弧
    # 3. 如果是"("，加入棧頂，如果是")"，看棧是否為空，為空則匹配失敗，否則pop棧頂
    # 4. 最後檢查棧是否為空以及標記符號是否為True，為空則匹配成功，反之失敗
    :param symbolString:
    :return:
    """
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        if symbolString[index] == "(":
            s.push("(")
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index += 1
    if balanced and s.isEmpty():
        balanced = True
    else:
        balanced = False
    return balanced

print(parChecker1(""))

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        if symbolString[index] in "([{":
            s.push(symbolString[index])
        else:
            if s.isEmpty():
                balanced
            else:
                top = s.pop()
                if not matches(top, symbolString[index]):
                    balanced = False
        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("[{()]"))
print(parChecker("([{)]}"))