Code to check whether a String contains balanced braces or not

balanced.rb

# Code to check whether a String contains balanced braces or not
# Author: Srikanth P Shreenivas : srikanthps (at) yahoo (dot) com

$num_threads = 2

# Finds the unbalanced braces in given string. If string is balanced, will return empty string
# Eg: If input is "{}{", then output will be "{">"
#     If input is "{}{}", then, output will be ""
#     If input is "}{", then, output will be "}{"
#     If input is "}{}", then, output will be "}"
def unbals(input)
  stack = []
  input.each_char do |c|
    stack.push c if (c == '{') || (c == '}' && (stack.last == '}' || stack.empty?))
    stack.pop    if (c == '}' && stack.last == '{')
  end
  return stack.join
end

# Splits a string in num chunks of equal size, last chunk will contain whatever is left
def split(str, num_chunks)

  chunk_size  = (str.size / num_chunks == 0 ? 1 : str.size / num_chunks) +
                (str.size % num_chunks == 0 ? 0 : 1)

  (1..num_chunks).collect do |n|
    str[(n-1)*chunk_size...(n)*chunk_size]
  end.compact
end

# === Checks whether string contains balanced braces or not ====
# Logic here is to split "str" into N chunks where N is number of threads we
# want to use for parallel processing, then, find out unbalanced portions of
# each chunk.  We then combine unbalanced portions of each chunk, and check
# whether that is balanced or not. If it is, then, we know whole string was
# balanced, else the whole string was unbalanced.
def balanced?(str)
  unbals(
    split(str, $num_threads).collect do |chunk|
      Thread.new { Thread.current[:output] = unbals(chunk)}
    end.each { |t| t.join }.collect { |t| t[:output] }.join
  ).empty?
end


## Test the code ##
input = ["{}", "{}{", "{{}}", "}{}{", "{{{{{ - balanced - }}}}}", "{{{}{{{}}}{}}}"]
biggest_input = input.max { |x, y| x.size <=> y.size }.size

input.each do |i|
  start = Time.now
  b = balanced?(i)
  finish = Time.now
  puts "#{i.ljust(biggest_input)} is\
        #{b ? ' ** _Balanced_ ** ' : ' ~~ Unbalanced ~~ '} \
        (Time taken: #{finish - start})"
end

Sample Output - JRuby 1.6.7

{}                       is          ** _Balanced_ **          (Time taken: 0.032)
{}{                      is          ~~ Unbalanced ~~          (Time taken: 0.0)
{{}}                     is          ** _Balanced_ **          (Time taken: 0.0)
}{}{                     is          ~~ Unbalanced ~~          (Time taken: 0.0)
{{{{{ - balanced - }}}}} is          ** _Balanced_ **          (Time taken: 0.015)
{{{}{{{}}}{}}}           is          ** _Balanced_ **          (Time taken: 0.0)

Sample Output - MRI 1.9.3-p125

{}                       is          ** _Balanced_ **          (Time taken: 0.0)
{}{                      is          ~~ Unbalanced ~~          (Time taken: 0.0)
{{}}                     is          ** _Balanced_ **          (Time taken: 0.0)
}{}{                     is          ~~ Unbalanced ~~          (Time taken: 0.0)
{{{{{ - balanced - }}}}} is          ** _Balanced_ **          (Time taken: 0.0)
{{{}{{{}}}{}}}           is          ** _Balanced_ **          (Time taken: 0.0)