中置表記：括弧をつけるべきかの判断

[ochaochaocha3]

中置記法表現を生成する際、演算子の優先順位や可換性を考慮して、括弧をつけるかどうかを決定する。

Rubyによるアルゴリズム実装例：

module Ast
  module Feature
    # 可換な2項演算子
    module Commutative
      def commutative?
        true
      end
    end

    # 非可換な2項演算子
    module Noncommutative
      def commutative?
        false
      end
    end

    module Parenthesization
      # 優先度を利用して括弧で囲む
      # @param [Object] element 対象要素
      # @return [Array] 括弧で囲んだかと変換後の結果
      def parenthesize_by_precedence(element)
        if element.precedence < self.precedence
          [true, "(#{element})"]
        else
          [false, element.to_s]
        end
      end
    end

    # 左結合の2項演算子
    module LeftAssociativeBinaryOperator
      include Parenthesization

      # 演算子を間に入れる
      # @return [String]
      def inject_operator(operator, inject_spaces = true)
        is_left_parenthesized, left_str = parenthesize_by_precedence(left)
        is_right_parenthesized, right_str_1 = parenthesize_by_precedence(right)
        right_str =
          if right.precedence == self.precedence && !right.commutative?
            "(#{right_str_1})"
          else
            right_str_1
          end

        [left_str, operator, right_str].join
      end
    end
  end

  # 加算
  class Add < Struct.new(:left, :right)
    include Feature::LeftAssociativeBinaryOperator
    include Feature::Commutative

    def precedence
      100
    end

    def to_s
      inject_operator('+')
    end
  end

  # 減算
  class Subtract < Struct.new(:left, :right)
    include Feature::LeftAssociativeBinaryOperator
    include Feature::Noncommutative

    def precedence
      100
    end

    def to_s
      inject_operator('-')
    end
  end

  # 乗算
  class Multiply < Struct.new(:left, :right)
    include Feature::LeftAssociativeBinaryOperator
    include Feature::Commutative

    def precedence
      200
    end

    def to_s
      inject_operator('*')
    end
  end

  # 除算
  class Divide < Struct.new(:left, :right)
    include Feature::LeftAssociativeBinaryOperator
    include Feature::Noncommutative

    def precedence
      200
    end

    def to_s
      inject_operator('/')
    end
  end
end

[ochaochaocha3]

同様の問題を扱っているRuby Quiz #148「Postfix to Infix」の一部を翻訳してみた。 https://gist.github.com/ochaochaocha3/ab0e7b576968453b236b80d88331941f

アルゴリズムは概ね合っていたが、一般に、左結合性（left associativity）と右結合性（right associativity）に基づいて括弧をつけるかどうか決めることができることが分かった。GoBCDiceのコードもこれに合わせて更新したい。

[ochaochaocha3]

端数処理方法を指定した除算の中置表記の実装で、四則演算の中置表記の実装は完了。まだ評価を実装していないランダム数値取り出しは一旦置いておき、加算ロールの中置表記の確認を行う。それで中置表記の実装は一旦完了とする。

[ochaochaocha3]

4ea20232a21c0cb7509409a8cfee8655dceb0875 で完了。