32

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

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

例子：

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

4

2 回答 2

57

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

  • 将计数器初始化为 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;
}

注意：上面的两个例子都假设括号是平衡的，所以没有进行数组边界检查。一个真正的实现会检查你没有跑出数组的末尾，如果你这样做了，就会抛出一个异常（或返回一个错误代码），表明括号在输入文本中是不平衡的。

于 2012-10-05T18:44:11.720 回答
-1 
private String GetJsonFromString(String source, String tagName)
    {
        int tagIndex = source.IndexOf(tagName);
        if (tagIndex < 0) return "";
        string rightSource = source.Substring(tagIndex).Trim();

        int openBrackeIndex = rightSource.IndexOf("{");
        if (openBrackeIndex < 0) return "";
        rightSource = rightSource.Substring(openBrackeIndex).Trim();

        int closePos = 0;
        int counter = 1;
        while (counter > 0)
        {
            char c = rightSource.ToCharArray()[++closePos];
            if (c == '{')
            {
                counter++;
            }
            else if (c == '}')
            {
                counter--;
            }
        }
        return rightSource.Substring(0, closePos + 1);
    }
于 2019-03-06T15:12:53.097 回答