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

Question

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

在给定文本文件中的左括号或右括号的位置的情况下,使用什么算法来查找匹配括号的位置？请记住,这些字符可以嵌套,因此只需向前或向后扫描文本,直到找到相反的字符是不够的.

例:

我最近在用Java 编写brainf*ck解释器时遇到了这个问题. [并且]在该语言中类似于while循环,并且可以嵌套.解释器需要找到匹配[或]取决于数据指针的值.有关嵌套的说明,请参阅ROT13示例代码.

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;
}

注意:上面的两个示例都假设括号是平衡的,因此不会进行数组边界检查.一个真正的实现将检查你是否没有运行数组的末尾,并抛出异常(或返回错误代码),指示如果你这样做,输入文本中的括号是不平衡的.