Find the first outer brackets

Question

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?

the solution is very nice... what do you mean by `cleaner` less code? different algo? — shahaf, May 06 '18 at 12:27
adding a stack is pointless. all you need is a count of opens. — Patrick Parker, May 06 '18 at 12:53
BTW, if you want a review of working code, you should post to the codereview stackexhange. not here. — Patrick Parker, May 06 '18 at 13:00

score 5 · Accepted Answer · answered May 06 '18 at 12:37

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

Thanks. This is much more elegant. And since the input is properly balanced, I can remove the code for corner case. — xingbin, May 06 '18 at 12:47

Shanu Gupta · Answer 2 · 2018-05-06T14:32:15.877

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

@NengLiu Welcome. Stack based solutions increases the space complexity. I've added a note for that. — Shanu Gupta, May 06 '18 at 12:53

score 1 · Answer 3 · answered May 06 '18 at 12:38

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

Yeah, the input is properly balanced. Thank you! – xingbin May 06 '18 at 12:47 — xingbin, May 06 '18 at 12:47

score 1 · Answer 4 · answered May 06 '18 at 22:46

I have eliminated some of the local variables which were required by the other solutions. For the conditional branch, there is only one simple operation: stack count is either incremented or decremented.

String input = "3[a2[c]]2[abc]3[cd]ef";
int first = input.indexOf('[');
int second = first;
for(int stack = 1; first >= 0 && stack > 0; second++) {     
    switch(input.charAt(second+1)) {
    case '[':
        stack++;
        break;
    case ']':
        stack--;
        break;
    }
}
System.out.println(first);
System.out.println(second);

Note: The above code relies on the fact that ] will always be balanced, as you stated.

Find the first outer brackets

4 Answers4

Linked