Please Forward: Ruby Quiz Submission

ruby-talk
1

From: John Browning <jb@poplar.com>
Date: May 8, 2006 12:19:12 PM CDT
To: submission@rubyquiz.com
Subject: Please Forward: Ruby Quiz Submission

I'm doing this for learning, but if you feel it worthy of submission please do so. It does a bit more error correction than solutions I've seen.

Many thanks for all the interesting and useful quizzes

allbests

code follows...................................

#!/usr/bin/ruby

# possible solution to Ruby Quiz 78 on Bracket Parsing
# If string validates, it prints it and returns 0
# If string can be corrected, it prints the corrected version and returns 0 (should perhaps return 1 or otherwise signal correction?)
# If string cannot be corrected -- eg because there are two or more possible places for the correcting bracket to go --
# it returns 1 and prints a string indicating possible corrections

# works pretty much like a recursive descent parser, except that instead of looking only at
# the leftmost token, it uses regular expressions to find bracketed pairs.
# It parses from the outside in, or, if there are two or more pairs at the same level, from the left (or not, depending on ruby implementation)
# Parsing like this makes it easier to keep track of where we are to do corrections

# TODO? It might be nice if this corrected and/or signalled all errors at once instead of just one level at a time. That would require moving error
# marking/correction to within parsing, so that parsing always returns a complete value. Errors would then presumably be signalled
# via global @err_val

# QUESTION: is BB+ legal? It's not in this implementation, but should it be? It would be more ecological...

class BracketParser
  # called with string to parse
  def initialize( toparse )
    @spec = toparse
  end

  # qc initiates parsing and prints a viable spec string or error.
  # returns 0 if string usable, else 1
  def qc
    begin
      print "#{parse( @spec )}\n"
      return 0
    rescue UncorrectableError => uerr
      uerr.show
      return 1
    end
  end

  # parse does what it says, recursively
  def parse( spec )
# print "parsing #{spec}\n"
    case spec
    when "B": # contents of box, which is also a leaf of parse tree, so stop recursion
      return spec
    when /^(\[.+?\]|\(.+?\)|\{.+?\})((\[.+?\]|\(.+?\)|\{.+?\})+)$/ # two boxes, parse each
      return parse( $1 ) + parse( $2 )
    when /^(\[)(.+?)(\])$/, /^(\()(.+?)(\))$/, /^(\{)(.+?)(\})$/ # just one box, parse contents
      return $1 + parse($2) + $3
    when /^(\[|\(|\{)(\[.+?\]$|\(.+?\)$|\{.+?\}$|B$)/ # extra opening bracket
      open, rest = $1, $2
      if ( rest =~ /^(\[.+?\]|\(.+?\)|\{.+?\})((\[.+?\]|\(.+?\)|\{.+?\})+)$/ )
        # can't correct if there are more than two possible boxes, so signal error and show possible closures
        raise UncorrectableError.new( open, rest, @spec )
      else
        # there's only one place the missing bracket can go, so put it there and keep parsing
        return open + parse( rest ) + (open == "["? "]": open == "("? ")": "}")
      end
    when /^(\[.+?\]|\(.+?\)|\{.+?\}|B)(\]|\)|\})$/ # extra closing bracket
      rest, close = $1, $2
      if ( rest =~ /^(\[.+?\]|\(.+?\)|\{.+?\})((\[.+?\]|\(.+?\)|\{.+?\})+)$/ )
        # can't correct if there are more than two possible boxes, so signal error and show possible closures
        raise UncorrectableError.new( close, rest, @spec )
      else
        # there's only one place the missing bracket can go, so put it there and keep parsing
        return (close == "]"? "[": close == ")"? "(": "{") + parse( rest ) + close
      end
    else
      # no clue, give up
      raise UncorrectableError.new( nil, nil, @spec )
    end
  end

end

class UncorrectableError < RuntimeError
  # shows errors that can't be corrected.
  # err can have one of three value:
  # nil means we don't know what to do about this error, so it just prints spec and admits defeat
  # an opening bracket means we lack a closing bracket but don't know where to put it, so print possibilities
  # a closing bracket is vice versa.
  # context is the part of the string where the error could be (and is ignored when err is nil)
  # spec is the total string
  def initialize( err, context, spec )
    @err = err
    @spec = spec
    if @err
      @context = context
      # split into boxes to show where missing bracket could go
      @possibles = @context.scan(/\[.+?\]|\(.+?\)|\{.+?\}/)
      # missing closing bracket
      if @err =~ /\[|\(|\{/ then
        @spec = @spec.gsub( (err + context), "*" )
        @fix = @err == "["? "]": @err == "("? ")": "}"
        @prompts = @err + @possibles.collect { |n| n + @fix + "?" }.to_s
      # missing opening bracket, which is pretty much the same apart from the order of things
      else
        @spec = @spec.gsub( (context + err), "*" )
        @fix = @err == "]"? "[": @err == ")"? "(": "{"
        @prompts = @possibles.collect { |n| @fix + "?" + n }.to_s + @err
      end
    end
  end

  def show
    if @err
      print "#{@spec.gsub( "*", @prompts )}\n"
    else
      print "#{@spec} just doesn't make sense at all\n"
    end
  end

end

box = BracketParser.new( ARGV.first.to_s )
box.qc

..................................................................................
John Browning
t: +44 20 7700 1230 f: +44 20 7700 5255

ยทยทยท

Begin forwarded message: