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

一尘不染

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

algorithm

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

给定文本文件中开头或结尾括号的位置，使用哪种算法查找匹配括号的位置？请记住，这些字符可以嵌套，因此只需在文本中向前或向后扫描，直到发现相反的字符不足。

例：

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

阅读 683

2020-07-28

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

注意：
上面的两个示例都假定括号是平衡的，因此不进行数组边界检查。真正的实现将检查您是否未在数组末尾运行，并抛出异常（或返回错误代码），该异常指示括号是否在输入文本中不平衡。

2020-07-28