4clojure #177 - Bracket Balancer

bracket_balancer.rb

#!/usr/bin/ruby
# Solution by Dean Radcliffe to 4clojure problem #177
# Disclaimer: not production-ready
# Strategy: Build a tree from parens. Return tree as truthy value, else nil
# TODO clojurify this 

require 'ostruct' #convenient hash-like data structure
require 'pp'      #pretty printer (optional)

def closer? char
  "}])".include? char
end

# aside from obvious purpose, can be used to ignore mate-less things
def mate_of char
 (@map ||= Hash[*"[]][{}}{())(".chars])[char]
end

# We will build a recursive tree of paren-representing nodes.
# The top-level node will be type '^', others will be '(' '[' or '{'.
def new_node opts={} 
  defaults = {type: '^', pos: 0, open: false, children: [], parent: nil}
  OpenStruct.new defaults.merge(opts)
end

# While tree-building, finding an opener creates a new child of current node
# A closer closes the open child, and moves you up a level in the tree
# Example: ([]{}) will be parsed into 
# ^
#   ()
#      []
#      {}
def try_append current, char, idx
  if closer? char
    if char == mate_of(current.type)
      current.open = false
      return current.parent
    else
      puts "Error: Can't close #{current.type} with #{char} at pos:#{idx+1}"
      return
    end
  else
    child = new_node type: char, pos: idx+1, open: true, parent: current
    current.children.push child
    return child
  end
end

# Traverses the enumerable passed, attempting to build a paren_tree.
# Returns nil if a valid paren_tree can't be built.
def paren_tree input_enum
  current = root = new_node()
  input_enum.each_with_index do |char, idx|
    if mate_of(char)
      current = try_append current, char, idx
      return nil unless current
    end
  end
  if current.open
    puts "Error: Can't leave open #{current.type}"
    return nil
  end

  (root.children.length > 0) ? root : nil
end

# Walks non-tail-recursively to create copy of paren_tree for printing.
def simplify root
  root.to_h.tap do |hash|
    hash.delete(:parent)
    hash.delete(:open)
    hash[:children] = hash[:children].map{|child| simplify child}
  end
end

# Contains inputs and expected results
# nil is for a failed parse, a num is for the # children of root node
examples = [
  ["]", nil],
  ["(", nil],
  ["()", 1],
  ["[]", 1],
  ["[]()", 2],
  ["([])", 1],
  ["([]{})", 1],
  ["([blah blah])", 1],
  ["([blah blah)]", nil],
  ["(])", nil],
  ["({)}", nil],
  ["", nil],
  ["This string has no brackets.", nil],
  [<<-C
    class Test {
      public static void main(String[] args) {
        System.out.println("Hello world.");
      }
    }
  C
  ]+[1], 
  ["(start, end]", nil],
  ["())", nil],
  ["[ { ] } ", nil],
  ["([]([(()){()}(()(()))(([[]]({}()))())]((((()()))))))", 1],
  ["([]([(()){()}(()(()))(([[]]({}([)))())]((((()()))))))", nil],
  ["[", nil],
]

examples.each do |input, expected|
  puts "Trying: #{input}"
  result = paren_tree(input.each_char)
  if result==nil && expected==nil
    puts "Pass (empty): #{input}"
  elsif result && result.children.length==expected
    pp simplify(result)
    puts "Pass: #{input}"
  else
    puts "Fail: #{input} :#{result && result.children.length}"
    exit 1
  end
end

puts "\nAll good !\n\n"