中置記法から後置記法への変換

はじめに（中置記法と後置記法）

簡単に言うと，

中置記法: 被演算数の真ん中に演算子を置く書き方（1+2）
後置記法: 被演算数の後に演算子を置く書き方（1 2 +）

中期記法と後置記法があるので，当然前置記法もある．

前置記法: 被演算数の前に演算子を置く書き方（+ 1 2）

前置記法をポーランド記法，後置記法を逆ポーランド記法ともいう．どっちがポーランド記法でどっちが逆ポーランド記法なのか混乱するので，ここでは前置記法・後置記法と表現する．

Wikipediaに説明があるので，それを見るのがよいだろう．

プログラムの構成

rubyで作ってみた．

中置記法を表すクラスInfixNotationを用意する．インスタンス生成時に中置記法の数式を文字列で指定する．

InfixNotation.new '10+20'

InfixNotationには後置記法に変換するto_postfixメソッドを用意する．このメソッドが後置記法を表すクラスPostfixNotationを返す．

InfixNotation.new('10+20').to_postfix → PostfixNotation

中置記法または後置記法の数式は属性formulaの中に格納する．したがって

InfixNotation.new('10+20').formula → '10+20'
InfoxNotation.new('10+20').to_postfix.formula → '10 20 +'

となる．

実行環境

以下の通り．

WindowsXP SP2+月次パッチたくさん
cygwin 1.5.25
cygwin版ruby 1.8.7

テスト用プログラム

最近流行のテストファーストということで，test/unitを使ってテスト用のスクリプトを作っておこう．このテスト用スクリプトがエラーなく動けばOKだ．

TestInfixNotation.rb：

#! /usr/bin/ruby -Ks

require 'test/unit'
require 'InfixNotation'
require 'PostfixNotation'
require 'NotationException'

class TestInfixNotation<Test::Unit::TestCase
  def setup
    @notation=InfixNotation.new
  end

  def test_accessor1
    @notation.formula='1+2'
    assert_equal '1+2',@notation.formula
  end

  def test_to_postfix1_1
    @notation.formula='1'
    assert_equal '1',@notation.to_postfix.formula
  end

  def test_to_postfix1_2
    @notation.formula=''
    assert_equal '',@notation.to_postfix.formula
  end

  def test_to_postfix1_3
    @notation.formula='+1'
    assert_equal '1 +',@notation.to_postfix.formula
  end

  def test_to_postfix1_4
    @notation.formula='-10'
    assert_equal '10 -',@notation.to_postfix.formula
  end

  def test_to_postfix1_5
    @notation.formula='-10+5'
    assert_equal '10 - 5 +',@notation.to_postfix.formula
  end

  def test_to_postfix2_1
    @notation.formula='1+2'
    assert_equal '1 2 +',@notation.to_postfix.formula
  end

  def test_to_postfix2_2
    @notation.formula='1+20-3'
    assert_equal '1 20 + 3 -',@notation.to_postfix.formula
  end

  def test_to_postfix2_3
    @notation.formula='10+20+30+40'
    assert_equal '10 20 + 30 + 40 +',@notation.to_postfix.formula
  end

  def test_to_postfix3_1
    @notation.formula='1*2'
    assert_equal '1 2 *',@notation.to_postfix.formula
  end

  def test_to_postfix3_2
    @notation.formula='10*2/3'
    assert_equal '10 2 * 3 /',@notation.to_postfix.formula
  end

  def test_to_postfix4_1
    @notation.formula='10+20*30'
    assert_equal '10 20 30 * +',@notation.to_postfix.formula
  end

  def test_to_postfix4_2
    @notation.formula='1+20*3+40'
    assert_equal '1 20 3 * + 40 +',@notation.to_postfix.formula
  end

  def test_to_postfix4_3
    @notation.formula='1*2+3*4'
    assert_equal '1 2 * 3 4 * +',@notation.to_postfix.formula
  end

  def test_to_postfix5_1
    @notation.formula='(1+2)'
    assert_equal '1 2 +',@notation.to_postfix.formula
  end

  def test_to_postfix5_2
    @notation.formula='(1)'
    assert_equal '1',@notation.to_postfix.formula
  end

  def test_to_postfix5_3
    @notation.formula='(10+20)*30'
    assert_equal '10 20 + 30 *',@notation.to_postfix.formula
  end

  def test_to_postfix5_3_1
    @notation.formula='(1+2)+3'
    assert_equal '1 2 + 3 +',@notation.to_postfix.formula
  end

  def test_to_postfix5_3_2
    @notation.formula='1+(20+3)+40'
    assert_equal '1 20 3 + + 40 +',@notation.to_postfix.formula
  end

  def test_to_postfix5_4
    @notation.formula='1*(2+3)'
    assert_equal '1 2 3 + *',@notation.to_postfix.formula
  end

  def test_to_postfix5_5
    @notation.formula='(1+2)*(3+4)'
    assert_equal '1 2 + 3 4 + *',@notation.to_postfix.formula
  end

  def test_to_postfix5_6
    @notation.formula='((1+2)*(3+4))+((5+6)*7)'
    assert_equal '1 2 + 3 4 + * 5 6 + 7 * +',@notation.to_postfix.formula
  end
end