From: Stefano Taschini <taschini.mlist@...>
Date: 2006-05-08T15:35:26+09:00
Subject: Re: [QUIZ] Bracket Packing (#78)

------=_Part_7455_22523233.1147070122982
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

#!/usr/bin/env ruby

=3Dbegin rdoc

In order to correct a possibly ill-formed string, the syntactic tree
is constructed starting from the leaves. Well-formed parts of the tree
are inlined in the string, marked by < and >. At the beginning, only
the leaves are marked:

 Bracketing["[(B)(B)]"]
   # =3D> "[(<B>)(<B>)]"

Then, the tree is grown from the leaves:

 Bracketing["[(B)(B)]"].grow_tree
   # =3D> "<[(B)(B)]>"

If the initial string is well-formed the inlined tree includes the
whole string, as in the case above. If the string is ill-formed, then
more than one tree fragmens are left:

 Bracketing['[{(B){(B)(B)}]'].grow_tree
   # =3D> "[{<(B)><{(B)(B)}>]"

Bracketing#fix_tree tries to add the missing bracket so that the
subtrees can be successfully merged:

 Bracketing['[{(B){(B)(B)}]'].grow_tree.fix_tree
   # =3D> "<[{(B)}{(B)(B)}]>"

Bracketing#balance wraps the whole thing up, returning a well-formed
string if the input string was successfully balanced and nil
otherwise.

 Bracketing['[{(B){(B)(B)}]'].balance
   # =3D> "[{(B)}{(B)(B)}]"

Invoking the program with the --test switch runs the test-suite. Else,
the first line of the input is parsed and possibly corrected. The exit
status is set in accordance with the success of the operation.

=3Dend

# Bracketing extends a string in the "bracket language" with inlined
# syntax tree, enclosed in "<" and ">"
class Bracketing < String

  # Replace each open bracket in a string with its closed equivalent.
  def close(string)
    string.tr('([{',')]}')
  end

  # Replace each closed bracket in a string with its open equivalent.
  def open(string)
    string.tr(')]}','([{')
  end

  # Construct a Bracketing object with marked leaves.
  def self.[](string)
    new(string.gsub(/B/,'<B>'))
  end

  # Expand the branches from the leaves.
  def grow_tree
    s =3D self
    while (z =3D s.
      gsub(/\(<((?:[^>]|><)*)>\)/) { "<(#{$1.gsub('><','')})>"}.
      gsub(/\[<((?:[^>]|><)*)>\]/) { "<[#{$1.gsub('><','')}]>"}.
      gsub(/\{<((?:[^>]|><)*)>\}/) { "<{#{$1.gsub('><','')}}>"}
    ) !=3D s
      s =3D z
    end
    z
  end

  # Find all possible corrections to an unbalanced Bracketing object
  # and select the one with lowest complexity.
  def fix_tree
    fixes =3D []
    scan(/<[^>]*>/) {
      l,m,r =3D $`,$&,$'
      a, b =3D l.gsub(/<[^>]*>/,''), r.gsub(/<[^>]*>/,'')
      if close(a + open(b[0,1]||'')).reverse =3D=3D b
        fixes << self.class.new(l + open(b[0,1]) + m + r).grow_tree
      end
      if a =3D=3D open(close(a[-1,1]||'') + b).reverse
        fixes << self.class.new(l + m + close(a[-1,1]) + r).grow_tree
      end
    }
    fixes.reject{|x| x['><']}.sort_by{|x| x.complexity}.first || self
  end

  # The complexity is proportional to the variance of the depth over
  # the leaves in the syntactic tree.
  def complexity
    current, data =3D 0, []
    scan(/./) {|c|
      current +=3D 1 if "{[("[c]
      current -=3D 1 if "}])"[c]
      data << current if c=3D=3D"B"
    }
    mean =3D data.inject{|a,x| a+x} / data.size().to_f
    data.inject(0){|a,x| a + (x-mean) ** 2}
  end

  # Return a balanced string or nil if self cannot be balanced.
  def balance
    z =3D grow_tree
    while true
      return $1 if z =3D~ /^<([^>]*)>$/
      s =3D z
      z =3D s.fix_tree
      return nil if z =3D=3D s
    end
  end

end

require 'test/unit'

class Bracketing::Test < Test::Unit::TestCase

  def test_construction
    assert_equal '[{(<B>}{(<B>)(<B>)}]', Bracketing['[{(B}{(B)(B)}]']
  end

  def test_grow_tree
    assert_equal '<{B}><(B)><[B]>', Bracketing['{B}(B)[B]'].grow_tree
    assert_equal '<[{(B)}{(B)(B)}]>', Bracketing['[{(B)}{(B)(B)}]'].grow_tr=
ee
    assert_equal '<{(B)}><{(B)(B)}>]', Bracketing['{(B)}{(B)(B)}]'].grow_tr=
ee
    assert_equal '[<{(B)}>{(<B><(B)>}]', Bracketing['[{(B)}{(B(B)}]'].grow_=
tree
  end

  def test_balance
    ref =3D '[{(B)}{(B)(B)}]'
    assert_equal ref, Bracketing['[{(B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['{(B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[(B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B){(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)(B}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)(B)]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)(B)}'].balance
    assert_equal nil, Bracketing['(B)}{(B)(B)}]'].balance
  end

end

Test::Unit.run =3D true
if __FILE__ =3D=3D $0
  if ARGV[0] =3D=3D '--test'
    ARGV.pop
    Test::Unit.run =3D false
  elsif out =3D Bracketing[gets.chomp].balance
    puts out
    exit 0
  else
    exit 1
  end
end

------=_Part_7455_22523233.1147070122982
Content-Type: application/octet-stream; name=fixbrackets.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: f_56t4p1
Content-Disposition: attachment; filename="fixbrackets.rb"

#!/usr/bin/env ruby

=begin rdoc

In order to correct a possibly ill-formed string, the syntactic tree
is constructed starting from the leaves. Well-formed parts of the tree
are inlined in the string, marked by < and >. At the beginning, only
the leaves are marked:

 Bracketing["[(B)(B)]"]
   # => "[(<B>)(<B>)]"

Then, the tree is grown from the leaves:

 Bracketing["[(B)(B)]"].grow_tree
   # => "<[(B)(B)]>"

If the initial string is well-formed the inlined tree includes the
whole string, as in the case above. If the string is ill-formed, then
more than one tree fragmens are left:

 Bracketing['[{(B){(B)(B)}]'].grow_tree
   # => "[{<(B)><{(B)(B)}>]"

Bracketing#fix_tree tries to add the missing bracket so that the
subtrees can be successfully merged:

 Bracketing['[{(B){(B)(B)}]'].grow_tree.fix_tree
   # => "<[{(B)}{(B)(B)}]>"

Bracketing#balance wraps the whole thing up, returning a well-formed
string if the input string was successfully balanced and nil
otherwise.

 Bracketing['[{(B){(B)(B)}]'].balance
   # => "[{(B)}{(B)(B)}]"

Invoking the program with the --test switch runs the test-suite. Else,
the first line of the input is parsed and possibly corrected. The exit
status is set in accordance with the success of the operation.

=end

# Bracketing extends a string in the "bracket language" with inlined
# syntax tree, enclosed in "<" and ">"
class Bracketing < String

  # Replace each open bracket in a string with its closed equivalent.
  def close(string)
    string.tr('([{',')]}')
  end

  # Replace each closed bracket in a string with its open equivalent.
  def open(string)
    string.tr(')]}','([{')
  end

  # Construct a Bracketing object with marked leaves.
  def self.[](string)
    new(string.gsub(/B/,'<B>'))
  end

  # Expand the branches from the leaves.
  def grow_tree
    s = self
    while (z = s.
      gsub(/\(<((?:[^>]|><)*)>\)/) { "<(#{$1.gsub('><','')})>"}.
      gsub(/\[<((?:[^>]|><)*)>\]/) { "<[#{$1.gsub('><','')}]>"}.
      gsub(/\{<((?:[^>]|><)*)>\}/) { "<{#{$1.gsub('><','')}}>"}
    ) != s
      s = z
    end
    z
  end

  # Find all possible corrections to an unbalanced Bracketing object
  # and select the one with lowest complexity.
  def fix_tree
    fixes = []
    scan(/<[^>]*>/) {
      l,m,r = $`,$&,$'
      a, b = l.gsub(/<[^>]*>/,''), r.gsub(/<[^>]*>/,'')
      if close(a + open(b[0,1]||'')).reverse == b
        fixes << self.class.new(l + open(b[0,1]) + m + r).grow_tree
      end
      if a == open(close(a[-1,1]||'') + b).reverse
        fixes << self.class.new(l + m + close(a[-1,1]) + r).grow_tree
      end
    }
    fixes.reject{|x| x['><']}.sort_by{|x| x.complexity}.first || self
  end

  # The complexity is proportional to the variance of the depth over
  # the leaves in the syntactic tree.
  def complexity
    current, data = 0, []
    scan(/./) {|c|
      current += 1 if "{[("[c]
      current -= 1 if "}])"[c]
      data << current if c=="B"
    }
    mean = data.inject{|a,x| a+x} / data.size().to_f
    data.inject(0){|a,x| a + (x-mean) ** 2}
  end

  # Return a balanced string or nil if self cannot be balanced.
  def balance
    z = grow_tree
    while true
      return $1 if z =~ /^<([^>]*)>$/
      s = z
      z = s.fix_tree
      return nil if z == s
    end
  end

end

require 'test/unit'

class Bracketing::Test < Test::Unit::TestCase

  def test_construction
    assert_equal '[{(<B>}{(<B>)(<B>)}]', Bracketing['[{(B}{(B)(B)}]']
  end

  def test_grow_tree
    assert_equal '<{B}><(B)><[B]>', Bracketing['{B}(B)[B]'].grow_tree
    assert_equal '<[{(B)}{(B)(B)}]>', Bracketing['[{(B)}{(B)(B)}]'].grow_tree
    assert_equal '<{(B)}><{(B)(B)}>]', Bracketing['{(B)}{(B)(B)}]'].grow_tree
    assert_equal '[<{(B)}>{(<B><(B)>}]', Bracketing['[{(B)}{(B(B)}]'].grow_tree
  end

  def test_balance
    ref = '[{(B)}{(B)(B)}]'
    assert_equal ref, Bracketing['[{(B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['{(B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[(B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{B)}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B}{(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B){(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}(B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{B)(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B(B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)B)}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)(B}]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)(B)]'].balance
    assert_equal ref, Bracketing['[{(B)}{(B)(B)}'].balance
    assert_equal nil, Bracketing['(B)}{(B)(B)}]'].balance
  end

end

Test::Unit.run = true
if __FILE__ == $0
  if ARGV[0] == '--test'
    ARGV.pop
    Test::Unit.run = false
  elsif out = Bracketing[gets.chomp].balance
    puts out
    exit 0
  else
    exit 1
  end
end

------=_Part_7455_22523233.1147070122982--