检查括号是否平衡/匹配

Question

我有一些MS Word文档，已将整个内容转移到SQL表中。

这些内容包含许多方括号和花括号，例如：

[{a} as at [b],] {c,} {d,} etc 

我需要进行检查，确保括号匹配平衡，例如下面的内容应该返回false：

 - [{a} as at [b], {c,} {d,} 
 - ][{a} as at [b], {c,} {d,} 
 - [{a} as at [b],] {c,} }{d,

到目前为止，我已经提取了所有方括号并将它们的信息存储到 SQL 表中，如下所示： (段落编号、方括号类型、方括号位置、方括号级别)

3   [   8   1
3   ]   18  0
3   [   23  1
3   ]   35  0
7   [   97  1
7   ]   109 0
7   [   128 1
7   {   129 2
7   }   165 1
7   [   173 2
7   ]   187 1
7   ]   189 0
7   {   192 1
7   }   214 0
7   {   216 1
7   }   255 0
7   {   257 1
7   }   285 0
7   {   291 1
7   }   326 0
7   {   489 1
7   }   654 0

我不确定算法如何检查每段落中的括号是否平衡，并在其不平衡时给出错误消息。

欢迎提供建议！

编辑：

代码还需要适用于以下情况：

(段落编号，括号类型，括号位置，括号级别)

15  [   543 1
15  {   544 2
15  }   556 1
15  [   560 2
15  ]   580 1
15  ]   581 0
15  [   610 1
15  ]   624 0
15  [   817 1
15  ]   829 0

- viv_acious

---

括号不能在一个段落中打开，然后在另一个段落中关闭，这是吧？ - Martin Smith

没错！每个段落都应该自我平衡。 - viv_acious

Answer 1

这必须在SQL服务器上吗？

一个简单的解决方案是使用通用编程语言并使用堆栈。

• 逐个字符读取字符串
• 如果遇到开括号，则将其推入堆栈。
• 如果遇到闭括号，则弹出堆栈。

如果所有括号都匹配，则为：

• 在完全阅读段落后，堆栈为空。

除非在该过程中发生以下情况之一：

• 您必须弹出空堆栈
• 弹出的括号与闭括号不匹配

不建议使用正则表达式来匹配括号，它们不应该被这样使用。

- mzzzzb

Answer 2

我不确定你有哪些工具可用，但这里有一个经过测试的JavaScript函数，可以验证所有（可能嵌套的）方括号和花括号是否匹配：

function isBalanced(text) {
    var re = /\[[^[\]{}]*\]|\{[^[\]{}]*\}/g;
    while (text.search(re) !== -1) { text = text.replace(re, ''); }
    return !(/[[\]{}]/.test(text))
}

它的工作原理是通过迭代地匹配和删除最内层的平衡对，直到没有匹配的对剩余为止。完成后，会进行测试以查看是否还有方括号或花括号。如果有任何剩余，则函数返回false，否则返回true。您应该能够在几乎任何语言中实现此功能。

请注意，这假定方括号和花括号对不会交错，如下所示：[..{..]..}

希望这可以帮助您。

附加说明：扩展版本适用于：（），{}，[]和<>

上述方法可以轻松扩展以处理测试所有四种匹配括号类型：（），{}，[]和<>，如下所示：

/*#!(?#!js\/g re Rev:20150530_121324)
    # Innermost bracket matching pair from 4 global alternatives:
      \( [^(){}[\]<>]* \)  # Either g1of4. Innermost parentheses.
    | \{ [^(){}[\]<>]* \}  # Or g2of4. Innermost curly braces.
    | \[ [^(){}[\]<>]* \]  # Or g3of4. Innermost square brackets.
    | \< [^(){}[\]<>]* \>  # Or g4of4. Innermost angle brackets.
!#*/
function isBalanced(text) {
    var re = /\([^(){}[\]<>]*\)|\{[^(){}[\]<>]*\}|\[[^(){}[\]<>]*\]|\<[^(){}[\]<>]*\>/g;
    while (text.search(re) !== -1) { text = text.replace(re, ''); }
    return !(/[(){}[\]<>]/.test(text));
}

请注意，正则表达式已在扩展模式C注释中记录。

编辑20150530： 扩展以处理所有四种匹配括号类型的混合：（），{}，[]和<>。

- ridgerunner

---

在一个编程挑战中发现这个问题，我想出了一个使用栈的解决方案：https://jsfiddle.net/felixcriv/0Ly8ssjq/ - Felix

Answer 3

我同意用户mzzzzb的观点。我一直在解决一个编程挑战，它有些类似，并用JavaScript提出了以下解决方案：

function isBalanced(str) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  return str.split('').reduce((res, e) => {
    // if its opening, put in stack
    if (['(', '{', '['].includes(e)) stack.push(e);
    // if closing, compare thru stack
    else if ([')', '}', ']'].includes(e)) {
      if (stack.pop() !== pairs[e]) return false;
    }
    return res;
    // stack must also be empty
  }, true) && stack.length === 0;
}

- Mike Fleming