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

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.