【JavaScript 算法】栈与队列：解决括号匹配问题

🔥 个人主页：空白诗

在编程中，括号匹配问题是一类常见的算法题，通常用于验证括号的正确性，即检查括号是否成对出现且嵌套正确。栈（Stack）是一种非常适合解决括号匹配问题的数据结构。本文将详细介绍如何使用栈来解决括号匹配问题的原理、实现及其应用。

---

一、算法原理

括号匹配问题可以通过栈的数据结构来解决。栈是一种后进先出（LIFO，Last In First Out）的数据结构，非常适合处理嵌套和匹配问题。其基本思想是：

1. 遍历字符串中的每个字符。
2. 如果遇到左括号，将其压入栈中。
3. 如果遇到右括号，检查栈顶元素是否为对应的左括号。如果是，则将栈顶元素弹出；否则，括号不匹配。
4. 最终，栈应为空。如果栈不为空，则括号不匹配。

---

二、算法实现

以下是使用栈解决括号匹配问题的JavaScript实现：

/*** 检查括号是否匹配* @param {string} s - 包含括号的字符串* @return {boolean} - 括号是否匹配*/
function isValid(s) {const stack = []; // 初始化栈const map = {'(': ')','[': ']','{': '}'}; // 配对括号映射for (let i = 0; i < s.length; i++) {const char = s[i];if (map[char]) {// 如果是左括号，将其压入栈中stack.push(char);} else {// 如果是右括号，检查栈顶元素是否匹配const top = stack.pop();if (map[top] !== char) {return false; // 括号不匹配}}}return stack.length === 0; // 如果栈为空，括号匹配
}// 示例
const s1 = "({[]})";
const s2 = "({[})";
console.log(isValid(s1)); // 输出: true
console.log(isValid(s2)); // 输出: false

1. 函数定义与参数：

   • isValid(s)：检查括号是否匹配，接受包含括号的字符串作为参数。

2. 初始化栈和配对括号映射：

   • const stack = [];：初始化一个空栈。
   • const map = { '(': ')', '[': ']', '{': '}' };：定义配对括号的映射。

3. 遍历字符串中的每个字符：

   • for (let i = 0; i < s.length; i++)：遍历字符串。

4. 处理左括号：

   • if (map[char])：如果字符是左括号，将其压入栈中。

5. 处理右括号：

   • else：如果字符是右括号，检查栈顶元素是否匹配。
   • const top = stack.pop();：弹出栈顶元素。
   • if (map[top] !== char)：如果栈顶元素不匹配当前右括号，返回false。

6. 最终检查栈是否为空：

   • return stack.length === 0;：如果栈为空，括号匹配；否则，括号不匹配。

---

三、应用场景

1. 编译器和解释器：在编译器和解释器中，检查代码中的括号匹配是语法分析的重要步骤。
2. 文本编辑器：文本编辑器通常提供括号匹配的功能，帮助用户编写正确的代码。
3. 数学表达式：在处理数学表达式时，括号匹配是确保表达式合法性的重要检查。

---

四、总结

栈是一种非常适合解决括号匹配问题的数据结构，通过将左括号压入栈中，并在遇到右括号时进行匹配，可以有效地检查括号是否匹配。理解和掌握栈的基本操作，可以解决许多实际编程问题，如括号匹配、表达式求值等。

---