This 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 
string 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