中置記法から後置記法への変換−スタックと再帰編−

スタックと再帰を使った変換方法

ループではなく再帰を使ってみる．大まかなやり方は以下の通り．

変換元の中置記法が空だったらスタックの内容を上から連結して返却値とする（終了条件）
変換元の中置記法の先頭の値を取出す
取出した値が数値だったら，空白文字をつけて返却
取出した値が'('だったら，スタックへ積む．返却値は''（長さ0の文字列）
取出した値が')'だったら
1. '('が出てくるまでスタックから値を取出し連結して返却値とする
2. スタックから取出した'('は捨てる
取出した値が演算子だったら，以下の全ての条件が成立する間，スタックから要素を取り出し連結して返却値とする
1. スタックが空ではない
2. スタックの一番上の値の優先度 >= 中置記法から取り出した値の優先度
  優先度は，乗除算（*,/） > 加減算（+,-） > 括弧（(,)）．
先頭の値を消去．新しい引数として自分自身を呼ぶ

スタックとループ編と異なるのはInfixNotation.rbのみで，PostfixNotation.rb，NotationException.rbは同一である．以下，ソースはInfixNotation.rbのみ提示する．

InfixNotation.rb:

#! /usr/bin/ruby -Ks

class InfixNotation
  attr_accessor :formula

  def initialize(formula='')
    self.formula=formula
  end

  def to_postfix
    PostfixNotation.new self.infix2postfix(self.formula,Array.new)
  end

  def infix2postfix(formula,stack)
    priority={'*'=>2,'/'=>2,'+'=>1,'-'=>1,'('=>0,')'=>0}
    operator=%r{[#{Regexp.escape(priority.keys.to_s)}]}
    first=%r{^(\d+|#{operator})}

    if formula.empty? #終了条件
      stack.reverse.join(' ')
    else
      case c=formula[first]
      when /\d+/
        c+' '
      when '('
        stack.push c
        ''
      when ')'
        ret=''
        ret<<stack.pop+' ' until stack.last=='('
        stack.pop
        ret
      when operator
        ret=''
        ret<<stack.pop+' ' while not stack.empty? and priority[stack.last]>=priority[c]
        stack.push c
        ret
      else
        raise NotationException
      end<<infix2postfix(formula.sub(first,''),stack)
    end.strip #最後に付く不要な空白を削除
  end
end

上記ソースでは変換する中置記法を文字列として扱い，変換する関数infix2postfixへ引数として与えている．オブジェクトとして扱ったソースは以下の通り．

InfixNotation.rb（オブジェクト版）:

#! /usr/bin/ruby -Ks

class InfixNotation
  attr_accessor :formula

  def initialize(formula='')
    self.formula=formula
  end

  def to_postfix
    PostfixNotation.new self.infix2postfix(Array.new)
  end

  def infix2postfix(stack) #引数formulaはなくなり，stackのみ
    priority={'*'=>2,'/'=>2,'+'=>1,'-'=>1,'('=>0,')'=>0}
    operator=%r{[#{Regexp.escape(priority.keys.to_s)}]}
    first=%r{^(\d+|#{operator})}

    if self.formula.empty? #自身のformula属性を見る
      stack.reverse.join(' ')
    else
      case c=self.formula[first]
      when /\d+/
        c+' '
      when ')'
        ret=''
        ret<<stack.pop+' ' until stack.last=='('
        stack.pop
        ret
      when '('
        stack.push c
        ''
      when operator
        ret=''
        ret<<stack.pop+' ' while not stack.empty? and priority[stack.last]>=priority[c]
        stack.push c
        ret
      else
        raise NotationException
      end<<InfixNotation.new(self.formula.sub(first,'')).infix2postfix(stack) #新しいInfixNotationのインスタンスを作成して後置記法に変換
    end.strip
  end
end

テスト

単体テスト用のプログラムTestInfixNotation.rbを使ってテストをしよう．InfixNotation.rb，PostfixNotation.rb，NotationException.rb，TestInfixNotation.rbを全て同じディレクトリに置きTestInfixNotation.rbを実行する．

$ TestInfixNotation.rb
Loaded suite ./TestInfixNotation
Started
......................
Finished in 0.015 seconds.

22 tests, 22 assertions, 0 failures, 0 errors

エラーなしで終了．