逆ポーランド記法

ふと、逆ポーランド記法ってのがあったなーと思い出したんだけど、アルゴリズムを全然忘れてたのでネットで検索して、Rubyで実装してみた。

参考にしたページ→ 数式を逆ポーランド法に変換するための事柄

class ReversePolish
  # 演算子の優先度
  OP = {
    '+' => 1,
    '-' => 1,
    '*' => 2,
    '/' => 2,
  }

  # @param expr [Array<String>]
  def initialize(expr)
    @expr = expr.dup
    @list = []
  end

  # 逆ポーランド記法に変換
  # @return [Array]
  def parse
    @list = []
    stack = []
    while v = @expr.shift
      # 演算子じゃなかったら出力に追加
      unless OP[v]
        @list.push v.to_i
        next
      end
      # 現在の演算子よりも優先度が低い演算子をスタックから取り出して出力に追加
      until stack.empty? || OP[v] > OP[stack.last]
        @list.push stack.pop
      end
      # 現在の演算子をスタックに積む
      stack.push v
    end
    # スタック内の演算子をすべて取り出して出力に追加
    until stack.empty?
      @list.push stack.pop
    end
    @list
  end

  # 実行
  # @return [Integer]
  def run
    stack = []
    until @list.empty?
      v = @list.shift
      # 演算子じゃなかったらスタックに積む
      unless OP[v]
        stack.push v
        next
      end
      # スタックから値を取り出して
      a, b = stack.pop(2)
      # 計算して結果をスタックに積む
      case v
      when '+'
        stack.push(a + b)
      when '-'
        stack.push(a - b)
      when '*'
        stack.push(a * b)
      when '/'
        stack.push(a / b)
      end
    end
    # 最終的にスタック内の値が答
    stack.pop
  end
end

rp = ReversePolish.new %w( 10 + 20 * 30 - 40 + 50 )
rp.parse  #=> [10, 20, 30, "*", "+", 40, "-", 50, "+"]
rp.run    #=> 620