algorithm - How do I find the position of matching parentheses or braces in a given piece of text?

Question

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.

Example:

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.

Answer 1

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.

• 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.
• When the counter reaches zero, you've found the matching closing parenthesis.

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.

• 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.
• When the counter reaches zero, you've found the matching open parenthesis.

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: 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.