08 | 面试题：判断括号字符串是否有效

在编程面试中，判断括号字符串是否有效是一个经典而常考的问题。它不仅考察了面试者对栈（Stack）这一数据结构的应用能力，还间接检验了面试者的逻辑思维和问题解决能力。这类问题通常要求判断一个包含圆括号()、方括号[]、花括号{}的字符串是否经过适当嵌套和配对后能够完全闭合。接下来，我们将从问题解析、解题思路、代码实现、优化方向及实际应用等多个方面深入探讨这一面试题。

一、问题解析

首先，明确问题的输入与输出：

• 输入：一个由圆括号()、方括号[]、花括号{}以及可能的其他字符组成的字符串。
• 输出：一个布尔值，表示该字符串中的括号是否有效。

有效的括号字符串需要满足以下条件：

1. 每个左括号（(、[、{）都必须有一个相对应的右括号（)、]、}）与之配对。
2. 括号必须按照正确的顺序嵌套，即左括号必须在其对应的右括号之前出现。

二、解题思路

解决这个问题的直观方法是使用栈这一数据结构。栈是一种先进后出（FILO）的数据结构，非常适合处理这种需要“后来先服务”的场景。具体步骤如下：

1. 初始化：创建一个空栈用于存放左括号。
2. 遍历字符串：对于字符串中的每个字符，
   • 如果是左括号（(、[、{），则将其压入栈中。
   • 如果是右括号（)、]、}），则检查栈是否为空以及栈顶的左括号是否与当前右括号匹配。
     • 如果栈为空，或者栈顶的左括号与当前右括号不匹配，则字符串无效，返回false。
     • 如果匹配，则从栈中弹出栈顶的左括号，继续遍历下一个字符。
3. 判断结果：遍历结束后，如果栈为空，说明所有左括号都找到了对应的右括号且正确配对，字符串有效，返回true；否则，字符串中存在未配对的左括号，返回false。

三、代码实现

以下是使用Python语言实现的示例代码：

def isValid(s: str) -> bool:
    stack = []  # 初始化空栈
    mapping = {'(': ')', '[': ']', '{': '}'}  # 定义括号映射关系
    for char in s:
        if char in mapping:  # 如果是左括号，则压入栈
            stack.append(char)
        elif char in mapping.values() and (not stack or mapping[stack.pop()] != char):  # 如果是右括号，但栈为空或栈顶不匹配
            return False
    return not stack  # 如果栈为空，则返回True；否则返回False
# 示例测试
print(isValid("()"))  # True
print(isValid("()[]{}"))  # True
print(isValid("(]"))  # False
print(isValid("([)]"))  # False
print(isValid("{[]}"))  # True

四、优化方向

虽然上述代码已经能够高效地解决问题，但在某些特定场景下，我们仍然可以考虑以下优化方向：

1. 错误处理：在实际应用中，可能需要对输入进行更严格的验证，比如非法字符的处理。
2. 内存使用：虽然在这个问题中栈的使用已经非常高效，但在处理极大规模数据时，可以考虑使用更紧凑的数据结构来减少内存占用。
3. 性能优化：对于极端长的字符串，可以考虑使用更高效的算法或数据结构来进一步提高性能。不过，在大多数情况下，上述实现已经足够高效。

五、实际应用

判断括号有效性在多种场景下都有实际应用，包括但不限于：

1. 编程语言解析：在编译器或解释器中，判断代码中的括号是否有效是语法分析的重要步骤。
2. 文本编辑器：许多文本编辑器提供自动匹配括号的功能，这背后就需要用到判断括号有效性的算法。
3. 配置文件解析：在处理JSON、XML等配置文件时，确保括号（或其他类似结构的分隔符）的正确性是非常重要的。
4. 数学表达式计算：在解析数学表达式时，首先需要验证括号的正确性，以确保运算顺序的正确执行。

通过这个问题，我们不仅能够掌握栈的基本用法，还能深刻理解数据结构如何在实际问题中发挥作用，从而提升自己的编程能力和问题解决能力。