Wednesday, October 01, 2014

Check if a String is Balanced on Brackets

Tried the source code beautifier and love it! For the first time, I was able to easily post Java code on blogspot. :)
The new post is a solution I gave out in a phone interview. Later I found somebody has posted similar solution on the Internet.
I felt glad to see my thoughts was so right at its first reaction.
Problem: please figure out if a given string is balanced on special brackets pairs.
the bracket pairs are () and [].
"abcdeee" is balanced.
"abc(deddd)ffsd" is balanced because ) closes (
"abc(dfsdfsd]dfsdfsd" is not balanced because ( has no closing ) and ] has no openning [
":abc([sdfdfd)]sdfdfs" is not balanced because the bracket can nest in another bracket but they can not overlap the others

Solution: using stack to check if the brackets are matching.

this code can be improved by using predefined string to compare run time string. e.g. leftB.euqals(tmp) instead of tmp.equals(leftB) to avoid null pointer exception.

static boolean isBalanced(String statement) {
         Stack<Character> sHelper = new Stack<Character>();
         Character tmp;
         Character leftP = new Character('(');
         Character rightP = new Character(')');
         Character leftB = new Character('[');
         Character rightB = new Character(']');
         if (statement == null) return false;
         for (int i=0;i<statement.length();i++){
             tmp = statement.charAt(i);
             if (tmp.equals(leftB) || tmp.equals(leftP)){
                 sHelper.push(tmp);
             }else if (tmp.equals(rightB) ){
                 if (!sHelper.isEmpty() && leftB.equals(sHelper.peek()))
                     sHelper.pop();
                 else
                 return false;
                 
             }else if (tmp.equals(rightP) ){
                 if (!sHelper.isEmpty() && leftP.equals(sHelper.peek()))
                     sHelper.pop();
                 else
                 return false;
             }
         }
         return sHelper.empty();
     }

No comments: