[分享]如何用JS匹配无序括号字符串？

如何使用正则表达式匹配无序括号字符串？

在JavaScript编程中，我们经常需要处理字符串，而验证字符串中是否包含有效的括号对是一个常见的需求。乍一看，这似乎可以通过简单的正则表达式轻松解决。然而，如果括号的出现顺序不固定，传统的正则表达式方法就会遇到挑战。

问题根源

为什么传统的正则表达式无法解决这个问题呢？让我们以 /^(\(\))*(\{\})*(\[\])*$/ 这个正则表达式为例，它试图匹配仅包含圆括号、花括号和方括号的字符串，并要求这些括号必须成对出现。这个正则表达式可以成功匹配像 "(){}[]" 这样的字符串，但对于 "{}()[]" 这样的字符串，它就无能为力了。

这是因为这个正则表达式强制要求括号按照特定的顺序出现，而我们实际希望匹配的是任何有效的括号组合，无论它们的顺序如何。

解决方案：栈与正则表达式的完美结合

为了解决这个问题，我们需要一种更灵活的方法，将栈和正则表达式结合起来。

1. 精准识别单个括号: 首先，我们需要一个正则表达式来准确识别字符串中的单个括号。例如，我们可以使用 /[(){}[\]]/ 来匹配圆括号、花括号和方括号。

2. 栈：记录括号的利器: 接下来，我们遍历整个字符串，并使用一个栈来跟踪遇到的括号。

   • 当遇到一个左括号时，将其压入栈中。

   • 当遇到一个右括号时，检查栈顶元素是否为对应的左括号。

     • 如果匹配，则将栈顶元素弹出，继续遍历字符串。

     • 如果不匹配，则表明括号不匹配，字符串无效。

3. 栈为空：有效性的最终判决: 最后，如果遍历完整个字符串后栈为空，则说明所有的括号都正确匹配，字符串有效。反之，则字符串无效。

代码示例：让理论照进现实

以下是使用JavaScript实现上述算法的代码：

function isValidBracketString(str) {
  const bracketMap = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  const stack = [];
  const bracketRegex = /[(){}[\]]/;

  for (let i = 0; i < str.length; i++) {
    const char = str[i];

    if (bracketRegex.test(char)) {
      if (bracketMap[char]) {
        // 如果是右括号
        if (stack.length === 0 || stack.pop() !== bracketMap[char]) {
          return false; // 栈为空或括号不匹配
        }
      } else {
        // 如果是左括号
        stack.push(char);
      }
    }
  }

  return stack.length === 0; // 栈为空则所有括号匹配
}

// 测试用例
console.log(isValidBracketString("(){}[]")); // true
console.log(isValidBracketString("{}()[]")); // true
console.log(isValidBracketString("{[()]}")); // true
console.log(isValidBracketString("(]")); // false
console.log(isValidBracketString("([)]")); // false
console.log(isValidBracketString("{[}")); // false

代码解析：深入理解算法的精髓

这段代码的核心思想是利用栈的后进先出特性来匹配括号。bracketMap 对象用于存储括号的对应关系，stack 数组用于模拟栈的操作。在遍历字符串的过程中，遇到左括号就入栈，遇到右括号就与栈顶元素比较，如果匹配则出栈，否则说明括号不匹配。

总结

通过将栈和正则表达式结合起来，我们可以有效地验证字符串中是否包含有效的无序括号对。这种方法不仅清晰易懂，而且可以轻松地扩展到其他类型的括号匹配问题。

常见问题解答

1. 问：为什么不能只使用正则表达式来解决这个问题？

   答：传统的正则表达式无法处理括号的嵌套和无序性，它只能匹配预定义的顺序。

2. 问：栈是如何帮助解决这个问题的？

   答：栈的后进先出特性与括号的匹配规则完美契合，左括号入栈，右括号出栈，可以有效地判断括号是否匹配。

3. 问：代码中的 bracketMap 对象有什么作用？

   答：bracketMap 对象用于存储括号的对应关系，方便在遇到右括号时快速查找对应的左括号。

4. 问：如何将这种方法应用于其他类型的括号匹配？

   答：只需修改 bracketMap 对象和 bracketRegex 正则表达式，就可以将其应用于其他类型的括号匹配。

5. 问：这种方法的时间复杂度是多少？

   答：由于只需要遍历一次字符串，因此时间复杂度为 O(n)，其中 n 为字符串的长度。