On 11/3/06, Ruby Quiz <james / grayproductions.net> wrote:
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Ross Bamford
>
> Note: This quiz isn't really as much work as it might seem!
>
> This quiz involves writing (in Ruby, of course) a compiler for basic arithmetic
> expressions. The output from this compiler should be an array of unsigned
> byte-sized ints, which can be fed into the included interpreter
> (http://www.rubyquiz.com/interp.rb) in order to execute the compiled expression.
>


Well... this took me longer than it probably should have.
I didn't find out about this:
http://en.wikipedia.org/wiki/Shunting_yard_algorithm
..until I was pretty much done anyway.

Also, helpful tip I'd like to send back to my past self.. Regular
expressions aren't powerful enough to find matched parentheses.

Anyway, thanks for the quiz. Fun stuff.

class Compiler
  def self.compile(input)
    @bytecodes = {'+' => 0x0a, '-' => 0x0b, '*' => 0x0c, '**' => 0x0d,
'/' => 0x0e, '%' => 0x0f}
    encode postfix(input)
  end

  def self.encode(tokens)
    tokens.collect do |token|
      number = token =~ /\-?\d+/ ? token.to_i : nil
      if (-32768..32767).include?(number)
        [0x01] + [number].pack('n').split(//).collect {|byte| byte[0]}
      elsif !number.nil? # long
        [0x02] + [number].pack('N').split(//).collect {|byte| byte[0]}
      else
        @bytecodes[token]
      end
    end.flatten
  end

  def self.postfix(infix)
    stack, stream, last, op = [], [], nil, nil
    tokens = infix.scan(/\d+|\*\*|[-+*\/()%]/)
    tokens.each_with_index do |token,i|
      case token
      when /\d+/; stream << token
      when *@bytecodes.keys
        if token == '-' and last.nil? || (last =~ /\D/ && tokens[i+1] =~ /\d/)
          tokens[i+1] = "-#{tokens[i+1]}"
        else
          stream << stack.pop while stack.any? && preceded?(stack.last, token)
          stack << token
        end
      when '('; stack << token
      when ')'; stream << op while (op = stack.pop) && (op != '(')
      end
      last = token
    end
    stream << op while op = stack.pop
    stream
  end

  def self.preceded?(last, current)
    ops = {'+' => 1, '-' => 1, '%' => 2, '/' => 2, '*' => 2, '**' =>
3, '(' => 0, ')' => 0}
    ops[last] >= ops[current] rescue true
  end
end