Rubyで逆ポーランド記法の計算機と変換器を作った

More than 1 year has passed since last update.

RUBY_VERSION >= '2.1.0' で動作を確認しています。


rpn.rb

require 'ripper'

class String
def to_rpn
RPN.new(self)
end
end

class RPN
attr_reader :queue

def self.calc(queue)
stack = []

until queue.empty?
stack << queue.shift

if %i(+ - * / ** << >> % & ^ |).include?(stack.last)
receiver, arg, op = stack.pop(3).map { |e| e.instance_of?(String) ? eval(e) : e }
stack << receiver.send(op, arg)
elsif %i(~ -@ +@).include?(stack.last)
receiver, op = stack.pop(2).map { |e| e.instance_of?(String) ? eval(e) : e }
stack << receiver.send(op)
end
end

stack.pop
end

def initialize(formula)
@formula = formula
stree = Ripper.sexp(@formula)
@queue = parse(stree[1..-1]).flatten
end

def parse(tree)
queue = []

case tree[0]
when :paren
queue << parse(tree[1..-1])
when :binary
return [parse(tree[1]), parse(tree[3]), tree[2]]
when :unary
return [parse(tree[2]), tree[1]]
when :@int
return tree[1].to_i
when :@float
return tree[1].to_f
when :@rational
return tree[1]
when :@imaginary
return tree[1]
else
if tree[0].instance_of?(Array)
queue << parse(tree[0])
else
raise "Parse failed. `#{@formula}' - #{tree.inspect}"
end
end

queue
end

def calc
RPN.calc(queue.dup)
end

def to_s
queue.join(' ')
end
end


数式を解析する部分は Ripper#sexp を使用しました。


使い方

String#to_rpn を使用して変換出来ます。

rpn = '1 + 2 + 3'.to_rpn

p rpn.queue #=> [1, 2, :+, 3, :+]
p rpn.calc #=> 6
puts rpn #=> 1 2 + 3 +

直接配列を渡して計算させることも出来ます。

p RPN.calc([3, 4, :*]) #=> 12

gemにもしてみました。(残念ながらrpnの名前は取られていました)

https://github.com/siman-man/rrpn


参考サイト

https://en.wikipedia.org/wiki/Reverse_Polish_notation