一道算法面试题：括号匹配问题

骑猪看日落 2022-05-27 07:15 214阅读 0赞

转载出处：http://mp.weixin.qq.com/s/PNhMY7FOFsXROeyohWts2w

还记得有一次笔试题，有一道括号匹配的算法题，当时没有学习数据结构和算法，思路很模糊，后来了解一些数据结构之后就有思路了，今天将解法写出来。

问题描述

> 给定一个字符串，里边可能包含“()”、"\{\}"、“\[\]”三种括号，请编写程序检查该字符串的括号是否成对出现。
> 
> 输出：
> 
> true：代表括号成对出现并且嵌套正确，或字符串无括号字符。
> 
> false：未正确使用括号字符。

# 分析 #

如果了解数据结构，那么应该知道，简单的采用一个栈的特性，就能解决该问题，左括号栈顶字符必须和第一个入栈的右括号字符匹配。

栈介绍：栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。  
栈的特性：后进先出（LIFO)

![70][]

栈示意

下面用一幅流程图来说明程序运行步骤：

![70 1][]

步骤流程图

# 代码实现 #

使用list来代替栈实现相同的操作。声明了几个变量：

*  BRANKETS：由配对的括号组成的字典，注意使用右括号作为key，因为我们要判断的是右括号是否与左括号匹配，在字典中找出与key对应的value简单，要是找value对应的key要复杂一些。
 *  BRANKETS\_LEFT与BRANKETS\_RIGHT分别存放左括号与右括号，用来判断字符属于哪个阵营。

#-*- coding: utf-8 -*-
    
    BRANKETS = {
       '}':'{',']':'[',')':'('}
    BRANKETS_LEFT, BRANKETS_RIGHT = BRANKETS.values(), BRANKETS.keys()
    
    def bracket_check(string):
        """括号匹配检测函数"""
        stack = []
        for char in string:
            # 如果是左括号
            if char in BRANKETS_LEFT:
                # 入栈
                stack.append(char)
            # 右括号
            elif char in BRANKETS_RIGHT:
                # stack不为空，并且括号匹配成功
                if stack and stack[-1] == BRANKETS[char]:
                    # 出栈
                    stack.pop()
                # 匹配成功
                else:
                    return False
    
        return not stack
    
    def main():
        print(bracket_check('{brace*&^[square(round)]end}'))
        print(bracket_check('{brace*&^[square(round])end}'))
    
    if __name__ == '__main__':
        main()

输出结果：

true
    false

--------------------

本文通过栈数据结构实现了括号匹配的判断，希望读者通过本文加深对栈的理解，并记住思路，没准下次面试时就会碰到这道题。

[70]: /images/20220527/681d299ebe6d41f2b57fce0edf781ae4.png
[70 1]: /images/20220527/8a3a2b5194514b6b9baac564814e3a33.png