algorithm - 如何在给定的一段文本中找到匹配的括号或大括号的位置？

Question

许多文本编辑器和 IDE 都有一个功能，当光标放在这些对中的开始或结束字符上时，会突出显示匹配的括号、方括号或大括号。

给定文本文件中左括号或右括号的位置，使用什么算法来查找匹配括号的位置？请记住，这些字符可以嵌套，因此仅向前或向后浏览文本直到找到相反的字符是不够的。

示例:

我最近在写 brainf*ck 时遇到了这个问题Java 解释器。该语言中的 [ 和 ] 类似于 while 循环，并且可以嵌套。解释器需要根据数据指针的值找到匹配的 [ 或 ]。查看ROT13 example code有关嵌套的说明。

Answer 1

给定字符数组中左括号的位置，有一个简单的算法使用计数器找到匹配的右括号。

• 将计数器初始化为 1。
• 在文本中向前(向右)循环。
  • 如果遇到另一个左括号，则增加计数器。
  • 如果遇到右括号，则递减计数器。
• 当计数器归零时，您就找到了匹配的右括号。

在代码中看起来像这样:

public int findClosingParen(char[] text, int openPos) {
    int closePos = openPos;
    int counter = 1;
    while (counter > 0) {
        char c = text[++closePos];
        if (c == '(') {
            counter++;
        }
        else if (c == ')') {
            counter--;
        }
    }
    return closePos;
}

在给定右括号的情况下查找匹配左括号位置的算法是相反的。

• 将计数器初始化为 1。
• 向后(向左)循环浏览文本。
  • 如果遇到左括号，则递减计数器。
  • 如果遇到右括号，则增加计数器。
• 当计数器归零时，您就找到了匹配的左括号。

在代码中:

public int findOpenParen(char[] text, int closePos) {
    int openPos = closePos;
    int counter = 1;
    while (counter > 0) {
        char c = text[--openPos];
        if (c == '(') {
            counter--;
        }
        else if (c == ')') {
            counter++;
        }
    }
    return openPos;
}

注意:上面的两个例子都假设圆括号是平衡的，所以没有进行数组边界检查。真正的实现会检查您是否没有超出数组的末尾，如果超出，则抛出一个异常(或返回错误代码)指示括号在输入文本中不平衡。