Loop for finding proper grouping brackets

Question

I've got this piece of code that you pass a string of special characters to and an index which points to a location in this string. The code will take the index, analyze the string, and return a new index of location of the proper grouping bracket. I.e., if index = 5, and my string is ![>[*[]^[#$]%]%]$%, I will be currently at ]. Then, I need to backtrace in the string to find its matching group bracket [. To do this, I've written the following method:

public static int jump(int current, String code){
    int count = 1;
    boolean flag = false;
    if('[' == code.charAt(current)){
      current++;
      while(flag == false){
        if('[' == code.charAt(current)) count++;
        else if(']' == code.charAt(current)) count--;
        if((']' == code.charAt(current)) && (count ==0)){
          flag = true;
          break;
        }
        current++;
      } 
    }

    else{
      current--;
      while(flag == false){
        if(']' == code.charAt(current)) count++;
        else if('[' == code.charAt(current)) count--;
        if(('[' == code.charAt(current)) && (count ==0)){
          flag = true;
          break;
        }
        current--;
      }
    }
    return current;
  }

But the more I look at this code the more I feel like "there's got to be a smarter way of doing it then a bunch of if-statements, a while loop, and a flag." But I'm not good enough at this point to figure out how to simplify what I've written (or the logic) into more readable, or smarter code. So I was hoping to find ways to improve this code since I find myself writing this kind of code from time to time and would like to improve the style if possible.

Answer 1

Consider

  public static int jump(int current, String code) {
    int count = 1;
    if (code.charAt(current) == '[') {
      while (true) {
        current++;

        if (code.charAt(current) == ']') {
          count--;

          if (count == 0) {
            break;
          }
        } else if (code.charAt(current) == '[') {
          count++;
        }
      }
    } else {
      do {
        current--;

        if (code.charAt(current) == '[') {
            count--;
        } else if (code.charAt(current) == ']') {
            count++;
        }
      } while (count != 0);
    }

    return current;
  }

You don't use the flag variable. We can get rid of it and just say while (true) or for (;;) with the same effect.

If you don't mind the extra comparisons, we can just use a do/while or even a regular while. Absent compiler optimization, the original code already does this many comparisons anyway.

If the extra comparison is too big a hit on performance, we don't need to check what the character at current is again. We can just check the count in the previous if, where you decrement it.

It's probably a trivial difference in performance, but if we exchange the two comparisons, it will do one fewer. That's because if the first comparison is true, we don't have to do the second comparison. And the originally second comparison will be true once more than the first.

Build once

If you are doing this a lot, you could do this faster by building an array of the same length as the string which stores the location of each match. Then this whole method could be as simple as

  public int jump(int current) {
    return matches[current];
  }

Or you could just say matches[current] in the calling code.

Building would involve something like

   Integer[] matches = new Integer[code.length()];

   Deque<Integer> bracketLocations = new ArrayDeque<>();
   for (int current = 0; current < matches.length; current++) {
     switch (code.charAt(current)) {
       case '[':
         bracketLocations.addFirst(current);
         break;
       case ']':
         matches[current] = bracketLocations.removeFirst();
         matches[matches[current]] = current;
         break;
     }
   }

After one scan, everything else is just an array access.

If matches is sparse, you might consider making it a HashSet instead of an array. The array is probably faster, but the HashSet probably uses less memory.

Answer 2

The most common approach to bracket matching is using a stack.

Unmatched brackets you encounter are pushed onto the stack. When encountering a matching bracket pop the stack (and verify if it's the correct type of bracket, maybe not needed in your case). If the stack is empty after finding a match, the last match was the position you were looking for.

This approach, as you can see, also immediately allows for bracket matching validation, and can handle different types of brackets in the same String

To boot, the code is simpler.

Note

When looking for a stack implementation in Java, you may come across java.util.Stack; don't use that, use java.util.ArrayDeque instead, as the Stack javadoc itself suggests.

Answer 3

Both loops use exactly the same principle, just in an opposite direction. You might consider generalizing this by declaring the startingBracketType, the oppositeBracketType and the offset in variables, and modify the loop accordingly:

// use ifs instead of ternaries if you prefer
char startingBracketType = code.charAt(current);
char oppositeBracketType = currentBracketType == '[' ? ']' : '[';
int offset = currentBracketType == '[' ? +1 : -1;

Then, write the loop once using the variables and

current += offset;

Furthermore, you don't actually use the flag. Thus, if you intend to break out with the flag, you don't need to break; - if you want to use break, remove the flag and use while(true). Or even better: use some sensible border checking in the while loop so that you also can handle malformed input.