题目：括号匹配

任务总览

题目描述

输入一个由 (​)​[​] 四种符号构成的字符串。判断其中的括号是否匹配，如果匹配，则输出 yes，否则输出 no。

示例：

• "([])"、"([()])"、"[((()))]"、"()[][][]()[]" 都是匹配的。
• "([)"、"([)]"、"([(]))" 都是不匹配的。

输入格式

• 输入一个仅由 (​)​[​] 组成的字符串，长度不超过 100。

输出格式

• 如果括号匹配，输出 "yes"。
• 如果括号不匹配，输出 "no"。

样例输入

([])

样例输出

yes

解题思路

1. ​使用栈（Stack）进行匹配检查​：
   • 遇到左括号 ( 或 [，入栈。
   • 遇到右括号 ) 或 ]，检查栈顶是否匹配：
     • 如果匹配（( 对应 )，[ 对应 ]），弹出栈顶元素。
     • 如果不匹配，则直接返回 "no"。
   • 如果遍历结束后栈非空，则返回 "no"，否则返回 "yes"。

算法步骤

1. ​初始化一个栈​，用于存储左括号 ( 和 [。
2. ​遍历输入字符串​：
   • 如果当前字符是 ( 或 [，入栈。
   • 如果当前字符是 )，检查栈顶是否为 (，是则弹出，否则返回 "no"。
   • 如果当前字符是 ]，检查栈顶是否为 [，是则弹出，否则返回 "no"。
3. ​遍历结束后检查栈是否为空​：
   • 若栈为空，说明括号完全匹配，返回 "yes"。
   • 若栈不为空，说明存在未匹配的左括号，返回 "no"。

时间复杂度分析

• ​遍历字符串一次​，每个字符最多 ​入栈 / 出栈一次​，时间复杂度为 ​**O(n)**​，其中 n 是字符串长度（最大 100）。
• ​使用栈存储括号​，空间复杂度为 ​**O(n)**​。

结论

• 该问题是 ​括号匹配问题​，可以通过 栈数据结构 高效解决。
• 采用 O(n) 时间复杂度 和 O(n) 空间复杂度 的算法，即可在 最坏情况下 处理最大长度 100 的输入字符串。