Find the first outermost brackets

91
May 06, 2018, at 5:38 PM

I need to find out the first outermost(not nested) brackets indexes.

For example

[]                         output: 0, 1
1[2]                       output: 1, 3
3[a2[c]]2[abc]3[cd]        output: 1, 7

I can find it by lots of conditions, current code:

public static void main(String[] args) {
    String input = "3[a2[c]]2[abc]3[cd]ef";
    int first = 0;
    int second = 0;
    int count = 0;
    boolean found = false;
    for (int index = 0; index < input.length(); index++) {
        if (input.charAt(index) == '[') {
            count++;
            if (found == false) {
                found = true;
                first = index;
            }
        } else if (input.charAt(index) == ']') {
            count--;
            if (found && count == 0) {
               second = index;
               break;
            }
        }
    }
    System.out.println(first);
    System.out.println(second);
}

Is there more clean way to do it?

Answer 1

Using a Stack may be more elegant:

String input = "3[a2[c]]2[abc]3[cd]ef";
Stack<Integer> stack = new Stack<> ();
int first = -1;
int second = -1;
for (int index = 0; index < input.length(); index++) {
    if (input.charAt(index) == '[') {
        stack.push(index);
    } else if (input.charAt(index) == ']' && !stack.isEmpty ()) {
        first = stack.pop ();
        if (stack.isEmpty ()) {
            second = index;
            break;
        }
    }
}
if (first >= 0 && second >= 0) {
    System.out.println(first);
    System.out.println(second);
} else {
  System.out.println ("not found");
}
Answer 2

I'd like to add that using stack maybe more elegant but comes with a added space complexity of O(n) which might not be desirable in all cases.

I'd just slightly minified the OP's original counter based strategy:

String input = "3[a2[c]]2[abc]3[cd]ef";
int first, second, index, indexOfFirstBracket = input.indexOf('['), count = 1;
for (index = indexOfFirstBracket + 1; index < input.length() && count != 0; index++) {
    if (input.charAt(index) == '[')
        count++;
    else if (input.charAt(index) == ']')
        count--;
}
first = indexOfFirstBracket;
second = index - 1;
System.out.println(first);
System.out.println(second);

Also here's a solution I made using the stack (I've added comments in the code for explanation):

 String input = "3[a2[c]]2[abc]3[cd]ef";
    int first, second, count;
    boolean found = false;
    Stack<Character> stack = new Stack<>();
    // first index will always be fixed
    int indexOfFirstBracket = input.indexOf('[');
    first = indexOfFirstBracket;
    //intialize the stack
    stack.push('[');
    int i;
    //loop from index after first [ character
    for (i = indexOfFirstBracket + 1; i < input.length() && !stack.isEmpty(); i++) {
        if (input.charAt(i) == '[' || (input.charAt(i) == ']' && stack.peek() == ']'))
            stack.push('[');
        else if (input.charAt(i) == ']' && stack.peek() == '[')
            stack.pop();
    }
    // second index when loop breaks
    second = i - 1;
    System.out.println(first);
    System.out.println(second);

I'm assuming input has balanced parenthesis. We can handle that if we want (if second == input.length).

Answer 3

Here's a stack-based solution (I hope it is self-explanatory)

Note: This assumes that the brackets in the input string is properly balanced (which is the case in your code).

String input = "3[a2[c]]2[abc]3[cd]ef";
Stack<Character> stack = new Stack<>();
int start = input.indexOf("["); //find first '['
System.out.println(start);
for(int i = start + 1   ; i < input.length(); i++) {
    if(input.charAt(i) == '[') {
        stack.push('[');
    } else if (input.charAt(i) == ']') {
        if (stack.isEmpty()) {
            System.out.println(i); //Matching ']' for our first '['
            break;
        }
        stack.pop();
    }
}
READ ALSO
Why unicode character \u0004 is not showing in Javafx TextArea

Why unicode character \u0004 is not showing in Javafx TextArea

I have algorithm which converts given unicode string to some other formUser has to provide this unicode string via TextArea

127
Reduce Complexity of Quicksort method

Reduce Complexity of Quicksort method

Hey guys I have a question I am trying to reduce the complexity of this code(at the bottom)My idea would be to remove the If clause in the while loop but I am kind of failing to do it

158
Get file tree with Gson library

Get file tree with Gson library

I'm trying to get a JSON file with the structure of a directory, including files and subdirectories recursively

166
Automated cluster deployment for Kafka

Automated cluster deployment for Kafka

For those interested I have created a fully automated cluster deployment solution for Apache Kafka and RedHat Linux based distributions

127