括号匹配算法：使用栈解决括号匹配问题

"括号匹配算法：使用栈解决括号匹配问题"\n\n本文介绍使用栈数据结构解决括号匹配问题，并提供详细的算法步骤和代码示例。\n\n问题描述\n从键盘输入一个包含有花括号{}、中括号{}、小括号()的字符串，判断括号是否正确匹配，输出判断结果。\n例如：输入"{d}{([a])({c})})"，则正确匹配。\n输入"[q{w(6[7]g)]}"，则错误匹配。\n\n算法步骤\n\n可以采用栈这种数据结构来解决括号匹配问题。\n\n1. 创建一个空栈。\n2. 遍历输入的字符串，对于每个字符：\n - 如果是左括号（包括花括号、中括号、小括号），将其压入栈中。\n - 如果是右括号，判断栈是否为空：\n - 如果栈为空，说明右括号没有对应的左括号，括号匹配不正确，返回False。\n - 如果栈不为空，将栈顶元素弹出并与当前右括号进行匹配，如果匹配成功则继续遍历，否则返回False。\n3. 遍历结束后，如果栈为空，则说明所有括号都成功匹配，返回True；否则返回False。\n\n采用栈的原因\n\n栈具有后进先出（LIFO）的特性，符合括号匹配的要求。遇到左括号时，将其入栈，遇到右括号时，将栈顶元素与当前右括号进行匹配，如果匹配成功则弹出栈顶元素，继续遍历；如果匹配失败或栈为空，则说明括号匹配不正确。\n\n因此，栈是解决括号匹配问题的合适数据结构。\n\n代码示例\npython\n# 使用栈解决括号匹配问题\ndef is_matched(s):\n stack = []\n for char in s:\n if char in '({[':\n stack.append(char)\n elif char in ')}]':\n if not stack:\n return False\n top = stack.pop()\n if (char == ')' and top != '(') or (char == '}' and top != '{') or (char == ']' and top != '['):\n return False\n return len(stack) == 0\n\n# 测试用例\ns = "[{d}](3){([a])({c})})"\nprint(is_matched(s)) # True\n\ns = "[q{w(6[7]g)]}"\nprint(is_matched(s)) # False\n\n\n总结\n\n本文介绍了使用栈解决括号匹配问题的算法，并提供了一些代码示例。栈的特性使其成为解决这类问题的理想数据结构。\n