Balanced Brackets

stacks_and_queuesThis challenge comes from HackerRank. The idea is to determine if a set of brackets is or is not balanced. Please take a look at the following URL for full specifications: https://www.hackerrank.com/challenges/balanced-brackets?h_r=internal-search

My sample data set follows:

7

{[()]}

{[(])}

{{[[(())]]}}

}

))]]}}

(){

()((

I was able to get almost there with my solution. The site contains 3 test cases which passed with my first implementation. I believe most test cases passed. After looking at discussions it became obvious that the last test case (number 7) was an issue. By changing the last time of my solution the issue was addressed.

Following is the output from the Eclipse IDE console:

7

{[()]}

{[(])}

{{[[(())]]}}

}

))]]}}

(){

()((

YES

NO

YES

NO

NO

NO

NO

My solution in Java follows:

package john.canessa.balanced.brackets;

import java.util.Scanner;

import java.util.Stack;

public class Solution {

/*

* determine if the string is balanced

*/

static String balanced(String s) {

// **** just in case (this is not needed for this solution) ****

if ((s == null) ||

(s.length() == 0) ||

((s.length() % 2) != 0)){

return “NO”;

}

Stack<Character> stack = new Stack<Character>();

// **** traverse the string ****

for (int i = 0; i < s.length(); i++) {

Character c = s.charAt(i);

switch (c) {

// **** left bracket ****

case ‘{‘:

case ‘[‘:

case ‘(‘:

stack.push(c);

break;

// **** right bracket ****

case ‘}’:

case ‘]’:

case ‘)’:

// **** unbalanced bracket ****

if (stack.isEmpty()) {

return “NO”;

}

// **** pop the next left bracket ****

Character fromStack = stack.pop();

// **** check matching left bracket ****

switch (c) {

case ‘}’:

if (!fromStack.equals(‘{‘)) {

return “NO”;

}

break;

case ‘]’:

if (!fromStack.equals(‘[‘)) {

return “NO”;

}

break;

case ‘)’:

if (!fromStack.equals(‘(‘)) {

return “NO”;

}

break;

// **** brackets do not match ****

default:

return “NO”;

}

break;

// **** character is NOT a bracket (should not happen) ****

default:

return “NO”;

}

}

              // **** all brackets match if stack is empty ****          

              return stack.isEmpty() ? “YES” : “NO”;

}

/*

* test code

* A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

*/

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int t = in.nextInt();

for(int a0 = 0; a0 < t; a0++){

String s = in.next();

System.out.println(balanced(s));

}

in.close();

}

}

In my first implementation, I just returned “YES” when parsing the test_end_conditionsstring finished. That is not correct because there can be additional unpaired brackets left in the stack. The simple change on the last line of the method addressed such condition. My solution was accepted.

One needs to always test for end condition cases. Always use simple and short sequences to check them.

If you have comments or questions on this or any other blog entry, please send me a message.

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.