Ruby script to convert a formula string to a RPN by binary tree.

infix2rpn_bt.rb

#! /usr/local/bin/ruby
#*********************************************************
# Ruby script to convert string to RPN (by binary tree).
# (Unary operators are not supported)
#*********************************************************

class Node
  attr_reader :expr

  def initialize(expr)
    # ノードを構成するデータ構造
    @expr  = expr  # このノードが表す式
    @left  = nil   # 左の子ノード
    @right = nil   # 右の子ノード
  end

  # 丸カッコ対応数チェック
  #
  # @return bool res: true(OK)|false(NG)
  def valid_bracket
    res = true
    nest = 0  # 丸カッコのネスト数

    begin
      @expr.split(//).each do |e|
        nest += 1 if e == "("
        if e == ")"
          nest -= 1
          break if nest < 0
        end
      end
      res = false unless nest == 0
      return res
    rescue => e
      raise
    end
  end

  # 解析（二分木に分割）
  def parse
    # 数式の最も外側のカッコを除去
    @expr = rm_most_outer_bracket(@expr)
    # 演算子の位置
    pos_operator = get_operator_pos(@expr)
    # 演算子が存在しない場合、項とみなす
    return if pos_operator < 0
    # 子ノード（左）
    @left = Node.new(rm_most_outer_bracket(@expr[0, pos_operator]))
    @left.parse
    # 子ノード（右）
    @right = Node.new(rm_most_outer_bracket(@expr[pos_operator + 1, @expr.size]))
    @right.parse
    # 演算子
    @expr = @expr[pos_operator]
  rescue => e
    raise
  end

  # 文字列生成（後置記法（逆ポーランド記法; RPN））
  def gen_post
    @left .gen_post if @left
    @right.gen_post if @right
    print "#{@expr} "
  rescue => e
    raise
  end

  # 文字列生成（中置記法（挿入記法））
  def gen_in
    print '(' if @left && @right
    @left .gen_in if @left
    print @expr
    @right.gen_in if @right
    print ')' if @left && @right
  rescue => e
    raise
  end

  # 文字列生成（前置記法（ポーランド記法））
  def gen_pre
    print "#{@expr} "
    @left .gen_pre if @left
    @right.gen_pre if @right
  rescue => e
    raise
  end

  # 値の計算
  #
  # @return float res: 計算結果
  def calc
    return @expr.to_f unless @left && @right
    res = 0

    begin
      operand_l = @left.calc
      operand_r = @right.calc
      case @expr
      when '+'; res = operand_l + operand_r
      when '-'; res = operand_l - operand_r
      when '*'; res = operand_l * operand_r
      when '/'; res = operand_l / operand_r
      end
      return res
    rescue => e
      raise
    end
  end

private
  # 数式の最も外側のカッコを除去
  #
  # @param  string expr: 数式文字列（カッコ除去前）
  # @return string expr: 数式文字列（カッコ除去後）
  def rm_most_outer_bracket(expr)
    res  = false  # true: 数式の最も外側にカッコあり, false: なし
    nest = 0      # カッコのネスト数

    begin
      # 最初の文字が "(" の場合、最も外側にカッコがあると仮定
      if expr[0] == "("
        res  = true
        nest = 1
      end
      # 2文字目以降、チェック
      expr[1..].split(//).each_with_index do |e, i|
        case e
        when "("
          nest += 1
        when ")"
          nest -= 1
          # 最後以外でカッコが全て閉じられた場合、最も外側にカッコはないと判断
          # 例:"(1+2)+(3+4)"などの場合
          if nest == 0 && i < expr.size - 2
            res = false
            break
          end
        end
      end
      # 最も外側にカッコがない場合、元の文字列をそのまま返す
      return expr unless res
      # カッコ内がからの場合、エラー
      puts "[ERROR] Empty bracket! #{expr}" if expr =~ /^\(\)$/
      # 最も外側のカッコを除去
      expr = expr[1..-2]
      # 更に最も外側にカッコが残っている場合、再帰的に処理
      expr = rm_most_outer_bracket(expr) if expr =~ /^\(.*?\)$/
      return expr
    rescue => e
      raise
    end
  end

  # 演算子の位置を取得
  #
  # @param string expr: 数式文字列
  # @return    int pos: 演算子の位置
  #                     （演算子が存在しない場合は -1 を返す）
  def get_operator_pos(expr)
    return -1 if expr.to_s.empty?
    pos     = -1  # 演算子の位置初期化
    nest    = 0   # カッコのネスト数
    pri_min = 4   # 演算子のこれまでで最も低い優先度
                  # （値が大きいほど優先度高）

    begin
      expr.split(//).each_with_index do |e, i|
        pri = 0  # 演算子の優先度
        case e
        when "="; pri = 1
        when "+"; pri = 2
        when "-"; pri = 2
        when "*"; pri = 3
        when "/"; pri = 3
        when "("; nest += 1; next
        when ")"; nest -= 1; next
        else; next
        end
        if nest == 0 && pri <= pri_min
          pri_min = pri
          pos = i
        end
      end
      return pos
    rescue => e
      raise
    end
  end
end

class Str2RpnBt
  def exec
    # 数式入力＆空白除去
    print 'Formula? '
    f = gets.chomp.gsub(/ /, "")
    # Node クラスのインスタンス化
    root = Node.new(f)
    # 丸カッコ対応数チェック
    unless root.valid_bracket
      puts "[ERROR] Brackets are unbalanced!"
      exit
    end
    # 解析（二分木分割）
    puts "---"
    puts "                Formula: #{root.expr}"
    root.parse
    # 文字列生成（後置記法（逆ポーランド記法; RPN））
    print "Reverse Polish Notation: "
    root.gen_post
    puts
    # 文字列生成（中置記法（挿入記法））
    print "         Infix Notation: "
    root.gen_in
    puts
    # 文字列生成（前置記法（ポーランド記法））
    print "        Polish Notation: "
    root.gen_pre
    puts
    # 値の計算
    print "                Answer = "
    print root.calc
    puts
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
    exit 1
  end
end

Str2RpnBt.new.exec if __FILE__ == $0