中置記法から後置記法への変換−スタックとループ編−

スタックとループを使った変換方法

まずはスタックとループを使って中置記法から後置記法へ数式を変換してみよう．やり方を箇条書きにすると以下の通り．

変換元の中置記法から取り出す値がある間，数値か演算子か括弧を取り出す．
取り出した値が数値だった場合：出力用文字列に連結
取り出した値が'('だった場合：スタックに積む
取り出した値が')'だった場合：
1. '('が出てくるまでスタックから値を取り出し，出力用文字列に連結
2. スタックから取り出した'('と，変換元の中置記法から取り出した')'は使わないので捨てる
取り出した値が演算子だったとき：以下の全ての条件が成立する間，スタックから要素を取り出して出力用文字列に連結
- スタックが空ではない
- スタックの一番上の値の優先度 >= 中置記法から取り出した値の優先度
  優先度は，乗除算（*,/） > 加減算（+,-） > 括弧（(,)）．
変換元の中置記法から取り出す値がなくなったら，スタックに残った値を全部出力用文字列に連結

ソース

以下の3ファイルを作る．それぞれ中置記法のクラス，後置記法のクラス，数式として不正な値を受け取った際に発生する例外のクラスである．全部同じディレクトリに置く．

InfixNotation.rb
PostfixNotation.rb
NotationException.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
  end

  def infix2postfix
    priority={'*'=>2,'/'=>2,'+'=>1,'-'=>1,'('=>0,')'=>0} #演算子と括弧の優先度
    operator=%r{[#{Regexp.escape(priority.keys.to_s)}]} #オペレータは演算子（+-*/）と括弧
    operator_or_operand=Regexp.union operator,/\d+/ # \d+はオペランド（被演算子）
    stack=Array.new
    out=''
    self.formula.gsub(operator_or_operand) do |c|
      #eachメソッドだと1行づつ（'10+1'.each → '10+1'）
      #each_byteメソッドでは1文字づつ（'10+1'.each_byte → '1' '0' '+' '1'）．
      case c
      when /\d+/
        out<<c+' '
      when '('
        stack.push c
      when ')'
        out<<stack.pop+' ' until stack.last=='('
        stack.pop
      when operator
        out<<stack.pop+' ' while not stack.empty? and priority[stack.last]>=priority[c]
        stack.push c
      else
        raise NotationException
      end
    end
    (out<<stack.reverse.join(' ')).strip #前後の余分な空白を削除
  end
end

PostfixNotation.rb：

#! /usr/bin/ruby -Ks

class PostfixNotation
  attr_accessor :formula

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

NotationException.rb：

#! /usr/bin/ruby -Ks

class NotationException<StandardError
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

エラーなしで終了．