Brackets balance checking


Brackets balance checking
=========================

Quiz ...... : write a method/function to check the blance of 
              (nested) brackets [] and () for a given string.
Example ... : "..([..])..((..))..[[]].."  ==> True
              "(()"  or "..[..(..]..).."  ==> False
Source .... : http://yen3rc.blogspot.com/2010/09/haskell-practice-parenthesis-balance.html


My Java/Haskell/Ruby solutions:

Java
----
  public static boolean check(String s) {
    assert(s != null);
    final Character OPEN_PARENTHESE = '(';
    final Character OPEN_BRACKET = '[';
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
      if (c == '(') {
        stack.push(OPEN_PARENTHESE);
      } else if (c == '[') {
        stack.push(OPEN_BRACKET);
      } else if (c == ')') {
        if (stack.empty() || stack.pop() != OPEN_PARENTHESE) {
          return false;
        }
      } else if (c == ']') {
        if (stack.empty() || stack.pop() != OPEN_BRACKET) {
          return false;
        }
      }
    }
    return stack.empty();
  }

Haskell
-------
check :: String -> Bool
check = check' [] where
  check' []       []       = True
  check' _        []       = False
  check' ss       ('(':xs) = check' ('(':ss) xs
  check' ss       ('[':xs) = check' ('[':ss) xs
  check' ('(':ss) (')':xs) = check' ss xs
  check' _        (')':xs) = False
  check' ('[':ss) (']':xs) = check' ss xs
  check' _        (']':xs) = False
  check' ss       (_  :xs) = check' ss xs

Ruby (version 1.9)
------------------
YEN3 said that no matter what language, they solve this almost the same way.
I disagree with her; in fact, with the power of recursive regular expression,
the ruby version could solve it on one liner code and without any explicit stack.

def check(s)
  s =~ /^(?<p>[^\(\)\[\]]*(\(\g<p>*\)|\[\g<p>*\])*)*$/
end

For more detail about recursive regular expression and 
detail analyze of this regex, have look at http://davidtran.doublegifts.com/blog/?p=162

One Response to “Brackets balance checking”

  1. yen3 Says:

    I see your ruby code, It is very surprise for me. I have to modify the sentences about “I think the problem is almost the same in any programming language”. Thanks you mention me to know it.

    btw, I am man. I am sorry to let you think I am woman. XD

Leave a Reply