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:
Post a Comment