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

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

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

Example:

最近写的时候遇到了这个问题脑残*ck http://en.wikipedia.org/wiki/BrainfuckJava 中的解释器。[ and ]在该语言中类似于 while 循环，并且可以嵌套。解释器需要找到匹配的[ or ]取决于数据指针处的值。请参阅ROT13 示例代码 http://en.wikipedia.org/wiki/Brainfuck#ROT13嵌套的说明。

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

• 将计数器初始化为 1。
• Loop forward (to the right) through the text.
  • 如果遇到另一个左括号，则增加计数器。
  • 如果遇到右括号，则递减计数器。
• 当计数器达到零时，您就找到了匹配的右括号。

在代码中，这看起来像：

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。
• Loop backwards (to the left) through the text.
  • 如果遇到左括号，则递减计数器。
  • 如果遇到右括号，则增加计数器。
• 当计数器达到零时，您就找到了匹配的左括号。

In code:

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

Note:上面的两个示例都假设括号是平衡的，因此不进行数组边界检查。真正的实现将检查您是否没有超出数组的末尾，并抛出异常（或返回错误代码），表明输入文本中的括号不平衡。