如何找到一个给定的一段文字匹配的括号或大括号的位置？ [英] How do I find the position of matching parentheses or braces in a given piece of text?

问题描述

大量的文本编辑器和IDE中有一个功能，突出匹配的括号，方括号或大括号，当光标置于无论是打开或关闭字符在这些对中的一个。

A lot of text editors and IDEs have a feature that highlights matching parentheses, square brackets, or curly braces when the cursor is placed over either the opening or closing character in one of these pairs.

使用何种算法来找到匹配的括号的位置，因为要么是在文本文件中左或右括号的位置？请记住，这些字符可以嵌套，所以索性扫描向前或向后的文本，直到找到相对字符是不够的。

What algorithm is used to find the position of the matching parenthesis, given the position of either an opening or closing parenthesis in a text file? Keep in mind that these characters can be nested, so simply scanning forward or backward through the text until you find the opposite character is insufficient.

示例：

写 brainf * CK 除preTER在Java中，当我最近就遇到了这个问题。 [和] 该语言类似于while循环，并可以嵌套。间preTER需要找到匹配的 [或] 取决于在数据指针的值。请参阅 ROT13例如code 嵌套的说明。

I recently ran into this problem when writing a brainf*ck interpreter in Java. [ and ] in that language are analogous to a while loop, and can be nested. The interpreter needs to find the matching [ or ] depending on the value at the data pointer. See the ROT13 example code for an illustration of nesting.

推荐答案

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

Given the position of an open parenthesis in an array of characters, there's a simple algorithm that uses a counter to find the matching close parenthesis.

• 在初始化一个计数器为1。
• 在循环着通过文字（右侧）。
  • 如果另一个打开的括号遇到，增加计数器。
  • 如果一个右括号遇到，减少计数器的值。
  • Initialize a counter to 1.
  • Loop forward (to the right) through the text.
    • If another open parenthesis is encountered, increment the counter.
    • If a closing parenthesis is encountered, decrement the counter.

    在$ C C本$看起来是这样的：

    In code this looks something like:

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

    该算法寻找给定一个右括号匹配左括号的位置是相反的。

    The algorithm for finding the position of the matching open parenthesis given a closing parenthesis is the opposite.

    • 在初始化一个计数器为1。
    • 循环向后（向左）通过的文本。
      • 如果左括号遇到，减少计数器的值。
      • 如果一个右括号遇到，增加计数器。
      • Initialize a counter to 1.
      • Loop backwards (to the left) through the text.
        • If an open parenthesis is encountered, decrement the counter.
        • If a closing parenthesis is encountered, increment the counter.

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

        注意：这两个上面的例子假设括号是平衡的，所以没有数组边界检查完成。真正的实现会检查你没有逃跑的数组的结束，并抛出一个异常（或返回错误code），表明括号是不平衡的输入文本，如果你做的。

        Note: Both of the examples above assume that parentheses are balanced, so no array bounds checking is done. A real implementation would check that you don't run off the end of the array, and throw an exception (or return an error code) that indicates that parentheses are unbalanced in the input text if you do.

        这篇关于如何找到一个给定的一段文字匹配的括号或大括号的位置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！