08 | 面试题：判断括号字符串是否有效-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

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

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

#### 一、问题解析

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

有效的括号字符串需要满足以下条件：
1. 每个左括号（`(`、`[`、`{`）都必须有一个相对应的右括号（`)`、`]`、`}`）与之配对。
2. 括号必须按照正确的顺序嵌套，即左括号必须在其对应的右括号之前出现。

#### 二、解题思路

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

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

#### 三、代码实现

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

```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. **数学表达式计算**：在解析数学表达式时，首先需要验证括号的正确性，以确保运算顺序的正确执行。

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

该分类下的相关小册推荐：

数据结构与算法(上)

数据结构与算法(下)

业务开发实用算法精讲

数据结构与算法之美

数据结构与算法(中)

编程之道-算法面试(下)

编程之道-算法面试(上)