Python面试题:使用栈处理括号匹配问题

- 日理万妓 2023-10-09 05:52 13阅读 0赞

括号匹配是栈应用的一个经典问题,

> 题目  
> 判断一个文本中的括号是否闭合,  
> 如: 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.  注意优化算法

> 更多学习资料请加添加作者微信：lockingfree获取

转载于:https://www.cnblogs.com/superhin/p/11454799.html