【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. 数学表达式：在处理数学表达式时，括号匹配是确保表达式合法性的重要检查。

四、总结

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