最近のキーワード

2006年07月22日

ポーランド記法<->逆ポーランド記法

http://jp.rubyist.net/magazine/?0015-EditorsNote
injectを使った実装と、tdp4rを使ったものを並べてみた。この程度なら構文解析使うと面倒になる。injectを使うとこうなる。
def postfix2prefix(expr)
  expr.split(/\s+/).inject([]){|acc,x|
    p acc
    case x
    when "+", "-", "*", "/"
      acc.push([acc.pop(),acc.pop(),x].reverse())
    else
      acc.push(x)
    end
  }.flatten().join(" ")
end

def prefix2postfix(expr)
  expr.split(/\s+/).reverse.inject([]){|acc,x|
    p acc
    case x
    when "+", "-", "*", "/"
      acc.push([acc.pop(),acc.pop(),x])
    else
      acc.push(x)
    end
  }.flatten().join(" ")
end

p postfix2prefix("1 2 2 / + 3 4 5 * + -")
p prefix2postfix("- + 1 / 2 2 + 3 * 4 5")
ついでに、tdp4rを使って素直に書くとこうなる。
# This script requires tdp4r-1.2.2 (http://rubyforge.org/projects/tdp4r/).
require 'tdp'
require 'tdputils'

translator = TDParser.define{|g|
  g.prefix_expr =
    g.op - g.prefix_expr - g.prefix_expr >> proc{|x|
      [x[1],x[2],x[0]].join(" ")
    } |
    g.int >> proc{|x| x[0] }

  g.postfix_expr =
    g.int - (g.postfix_expr - g.op)*0 >> proc{|x|
      x[1].inject(x[0]){|acc,y|
        [y[1],acc,y[0]].join(" ")
      }
    }

  g.int  = token(:int) >> proc{|x| x[0].value}

  g.op   = (token('+') | token('-') | token('*') | token('/')) >> proc{|x| x[0] }

  def translate_prefix_notation(str)
    tokenizer = TDPUtils::StringTokenizer.new({
      /\d+/ => :int,
    }, /\s+/)
    prefix_expr.parse(tokenizer.generate(str))
  end

  def translate_postfix_notation(str)
    tokenizer = TDPUtils::StringTokenizer.new({
      /\d+/ => :int,
    }, /\s+/)
    postfix_expr.parse(tokenizer.generate(str))
  end
}

p translator.translate_prefix_notation("- + 1 / 2 2 + 3 * 4 5")
p translator.translate_postfix_notation("1 2 2 / + 3 4 5 * + -")
posted by ttate at 15:22| ☔| Comment(0) | TrackBack(0) | Ruby | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。