From: Pablo Hoch <mel@...>
Date: 2006-01-09T06:42:06+09:00
Subject: Re: [QUIZ] Dice Roller (#61)

Here is my solution. I convert the expression into RPN (using the algorithm
described in the Wikipedia article) and then calculate it (I have added a
'd' method to Fixnum so that I can use it like the standard arithmetic
operators). My solution is not very strict, so it allows '%' as an alias for
100 anywhere in the expression (not just after a 'd'), but I think that
should not be a big problem. It also ignores other characters, so whitespace
is allowed anywhere.


Pablo

---

#!/usr/bin/ruby

class Fixnum
  def d(b)
    (1..self).inject(0) {|s,x| s + rand(b) + 1}
  end
end

class Dice

  def initialize(exp)
    @expr = to_rpn(exp)
  end
  
  def roll
    stack = []
    @expr.each do |token|
      case token
        when /\d+/
          stack << token.to_i
        when /[-+*\/d]/
          b = stack.pop
          a = stack.pop
          stack << a.send(token.to_sym, b)
      end
    end
    stack.pop
  end
  
  private
  
  def to_rpn(infix)
    stack, rpn, last = [], [], nil
    infix.scan(/\d+|[-+*\/()d%]/) do |token|
      case token
        when /\d+/
          rpn << token
        when '%'
          rpn << "100"
        when /[-+*\/d]/
          while stack.any? && stronger(stack.last, token)
            rpn << stack.pop
          end
          rpn << "1" unless last =~ /\d+|\)|%/
          stack << token
        when '('
          stack << token
        when ')'
          while (op = stack.pop) && (op != '(')
            rpn << op
          end
      end
      last = token
    end
    while op = stack.pop
      rpn << op
    end
    rpn
  end
  
  def stronger(op1, op2)
    (op1 == 'd' && op2 != 'd') || (op1 =~ /[*\/]/ && op2 =~ /[-+]/)
  end
  
end

if $0 == __FILE__
  d = Dice.new(ARGV[0])
  (ARGV[1] || 1).to_i.times { print "#{d.roll} " }
end