Python面試題:使用棧處理括号比對問題

括号比對是棧應用的一個經典問題,

題目

判斷一個文本中的括号是否閉合,

如: text = "({[({{abc}})][{1}]})2([]){({[]})}[]", 判斷所有括号是否閉合

思路

1. 使用棧後進先出的原則, 當字元是

   ([{

   之一時, 入棧
2. 當字元是

   )]}

   之一時, 判斷棧頂與目前字元是否是一對,
3. 如果比對, 彈出該括号(該括号匹已封閉), 繼續判斷下一個字元
4. 如果不比對, 直接return False

#!/usr/bin/python3

text = "({[({{abc}})][{1}]})2([]){({[]})}[]"


def is_closed(text:str) -> bool:  
    """
    判斷文本中括号是否封閉
    :param:text 包含括号的文本字元串
    :returns: True無括号或所有括号全部封閉
                   False 存在括号不封閉
    """
    stack = []  # 使用list模拟棧, stack.append()入棧, stack.pop()出棧并擷取棧頂元素
    brackets = {')':'(',']':'[','}':'{'}  # 使用字典存儲括号的對應關系, 使用反括号作key友善查詢對應的括号
    for char in text:
        if char in brackets.values():   # 如果是正括号,入棧
            stack.append(char)
        elif char in brackets.keys():  # 如果是反括号
            if brackets[char] != stack.pop():  # 如果不比對彈出的棧頂元素
                return False
    return True

print(is_closed(text))
           

1. 手寫代碼時建議盡量遵循PEP8規範, 寫出清晰高效的代碼
2. 傳回bool類型的用is_開頭
3. 建議寫上标準的docstring注釋(其他 # 注釋不用寫)
4. 注意優化算法