John Earles
1/8/2006 10:00:00 PM
Hi! This is my first entry to a RUBY-QUIZ. Sure I could have opted to use
'eval', but I figured I might as well learn a little about expression
parsing. Fun stuff!
My entry is focused around The Shunting Yard Algorithm, allowing me to
parse, transform and evaluate in the same step. I do not keep the 'postfix'
transform, so it is slightly inefficient to perform multiple 'rolls'. That
is an optimization for another day.
I also got to try out some new regexp stuff. Of particular note is the use
of (?=d) in the expression used to search for d's that need an implicit 1
lvalue. I was having problems with 5dddd7 type commands until I discovered
this allowed the target d NOT to be consumed by the regexp.
As a final note I am a Ruby Newbie, and a Java developer by day, so any tips
or comments on my coding would be appreciated. Thanks!
- John
-------------------
$DEBUG = false
# Dice Roller entry point
def roll_dice( dice_command, roll_count )
begin
puts "Executing #{roll_count} roll(s) of #{dice_command}"
results, total = Dice.new( dice_command ).roll( roll_count )
puts "Result: [#{results.join(', ')}] => #{total}"
rescue Exception => e
puts "Roll error: #{e}"
end
end
class Dice
# operator => [precendence, associativity]
@@operators = { "d" => [3, :right],
"*" => [2, :left] , "/" => [2, :left],
"+" => [1, :left] , "-" => [1, :left]
}
# Initialize the Stacks and load the dice instructions
def initialize( dice_command )
if $DEBUG
alias :d :dnd_roll_loaded
else
alias :d :dnd_roll_random
end
@operator_stack, @value_stack = [], []
prepare_instructions( dice_command )
end
def roll( roll_count )
results = (1..roll_count).collect { execute }
[results, results.inject {|sum, item| sum + item } || 0]
end
private
# The infix command is parsed into tokens and then executed using
# The Shunting Yard Algorithm. Evaluation is done "on-the-fly" as
# items are placed on the value stack (acting as the post-fix "output").
def execute
@operator_stack.clear
@value_stack.clear
# Process the tokens in L -> R order
# Look for non-digit characters and numbers
@instructions.scan(/\D|\d+/) do | token |
case token
when "("
@operator_stack.push token
when /\d+/ # any number
@value_stack.push token.to_i
when /[-\+*\/d]/ # the operators
finished = false
until finished or @operator_stack.empty?
if higher_operator(token)
finished = true
else
resolve_expression
end
end
@operator_stack.push token
when ")"
resolve_expression while @operator_stack.last != "("
@operator_stack.pop
else
raise "Invalid token found: #{token}"
end
end
resolve_expression while !@operator_stack.empty?
raise "Unexpected problem. #{@value_stack.size} values remain after
execution." unless @value_stack.size == 1
@value_stack.pop
end
def resolve_expression
opr, rhv, lhv = @operator_stack.pop, @value_stack.pop, @value_stack.pop
raise "No more values left for #{opr} to consume!" unless rhv && lhv
value = (opr == "d") ? value = d( lhv, rhv ) : lhv.send( opr, rhv )
@value_stack.push value.to_i
end
def dnd_roll_random( roll_count, die_value )
(1..roll_count).inject(0) { |value, item| value + ( rand(die_value) + 1
) }
end
def dnd_roll_loaded( roll_count, die_value )
roll_count * die_value
end
def higher_operator(opr)
if associativity(opr) == :left
precedence(opr) > precedence(@operator_stack.last)
else
precedence(opr) >= precedence(@operator_stack.last)
end
end
def precedence(opr)
@@operators[opr] ? @@operators[opr][0] : 0
end
def associativity(opr)
@@operators[opr] ? @@operators[opr][1] : :left
end
def prepare_instructions( dice_command )
# 1) Eliminate all whitespace.
# 2) Substitute d100 for d%
# 3) Insert the implied 1 if a d is the first character
# or is preceded by an operator other than ')'
@instructions = dice_command.gsub(/\s+/, '')
@instructions.gsub!(/d%/, 'd100')
@instructions.gsub!(/([-\+*\/(d]|\A)(?=d)/, '\11')
puts "Normalized instructions: #@instructions" if $DEBUG
raise "Unmatched left / right parenthesis" unless @instructions.scan(/\(/).size == @instructions.scan(/\)/).size
end
end
# Argument parsing
if $0 == __FILE__
raise "DiceRoller dice_command [roll_count=1]" unless (1..2).include?(
ARGV.length )
roll_dice(ARGV[0], ARGV[1] ? ARGV[1].to_i : 1)
end
--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.14.15/223 - Release Date: 06/01/2006