数据结构 栈 括号匹配

栈是一种常见的数据结构，它具有后进先出（Last In First Out，LIFO）的特点。在括号匹配问题中，我们可以使用栈来判断一个表达式中的括号是否匹配。具体步骤如下：

1.创建一个空栈。
2.从左到右扫描表达式中的每个字符。
3.如果当前字符是左括号（即'('、'{'或'['），则将其压入栈中。
4.如果当前字符是右括号（即')'、'}'或']'），则将栈顶元素弹出。如果弹出的左括号与当前右括号不匹配，则表达式不合法。
5.当扫描完整个表达式后，如果栈为空，则表达式合法；否则表达式不合法。

下面是一个Python实现的例子：

def is_valid(expr):
    stack = []
    for c in expr:
        if c in '({[':
            stack.append(c)
        elif c in ')}]':
            if not stack:
                return False
            if c == ')' and stack[-1] != '(':
                return False
            if c == '}' and stack[-1] != '{':
                return False
            if c == ']' and stack[-1] != '[':
                return False
            stack.pop()
    return not stack

# 测试
print(is_valid('[2 + (1 - 3)] * 4')) # True
print(is_valid('( ) )')) # False
print(is_valid('()()(())')) # True
print(is_valid('({}[])')) # True
print(is_valid(')(')) # False