Python递归实现括号匹配问题

2023-04-15 00:00:00 匹配递归括号

括号匹配指的是一个字符串中的括号是否匹配成对出现。例如，"()"、"(())"、"()()" 都是合法的匹配，而 ")("、"(()"、"())" 都不是合法的匹配。

Python递归实现括号匹配问题的思路是：使用栈（可以用 list 实现）存储左括号，遇到右括号时，如果栈顶匹配的左括号与右括号匹配，则弹出栈顶元素；否则，表示不合法。最后检查栈是否为空，如果为空，表示全部匹配成功，否则表示不合法。

代码示例：

def match_parenthesis(s):
    stack = []
    for c in s:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if len(stack) > 0 and stack[-1] == '(':
                stack.pop()
            else:
                return False
    return len(stack) == 0

上述代码中，stack[-1] 表示栈顶元素，stack.pop() 表示弹出栈顶元素。len(stack) == 0 表示栈是否为空。

接下来，可以使用如下代码进行测试：

print(match_parenthesis('()'))         # True
print(match_parenthesis('(())'))       # True
print(match_parenthesis('()()'))       # True
print(match_parenthesis(')('))         # False
print(match_parenthesis('(()'))        # False
print(match_parenthesis('())'))        # False
print(match_parenthesis('pidancode.com'))  # True
print(match_parenthesis('皮蛋编程'))   # True

输出结果如下：

True
True
True
False
False
False
True
True

可以看到，测试结果正确。

相关文章