[頭の体操] 逆ポーランド記法の列挙とその計算

列挙

[1, 2, 3, 4]を与えられた時に四則演算ですべてのパターンを列挙する

require "set"
NUMBERS = [1, 2, 3, 4]
SIGNS = %i[+ - / *]

results =
  NUMBERS.permutation(4).uniq.each.with_object(Set.new) do |numbers, results|
    (SIGNS * 3).permutation(3).uniq.each do |signs|
      a, b, c, d = numbers
      x, y, z = signs

      [c, d, x, y].permutation(4).uniq.each do |combination|
        next if combination.join.match(/\A([^\d]{2})/)

        results << ([a, b, *combination, z]).join(" ")
      end
    end
  end

# results.size => 7680

その計算

1 2 3 4 + - /を与えられた場合、-0.2を返す

require 'active_support/core_ext/object/blank'

class Rpn
  SIGNS = %i[+ - / *]

  class << self
    def calc(rpn_text)
      rpn = new(rpn_text)
      rpn.calc
    end
  end

  def initialize(rpn_text)
    @stack = notation_to_a(rpn_text)
  end

  def calc(this_stack = stack)
    return this_stack.first if this_stack.size == 1

    operator_at = this_stack.index{|x| SIGNS.include? x }
    operator = this_stack[operator_at]
    value = this_stack[operator_at - 2].send(operator, this_stack[operator_at - 1])
    this_stack[(operator_at - 2)..operator_at] = value

    return calc(this_stack)
  end

  private

  attr_reader :stack

  def notation_to_a(rpn_text)
    rpn_text.chars.select(&:present?).collect do |x|
      SIGNS.include?(x.to_sym) ? x.to_sym : x.to_f
    end
  end
end

Rpn.calc("1 2 3 4 + - /") # => -0.2