中置記法から逆ポーランド記法への変換

Scala 30分プログラム

30分プログラム、その690。中置記法から逆ポーランド記法への変換。
簡単かと思いきや、意外と難しい。とてもじゃないけど、括弧の対応はできなかった。

使い方

scala> val infix = new Infix()
infix: Infix = Infix@a32e6f

scala> infix += 1

scala> infix += '+'

scala> infix += 2

scala> infix += '*'

scala> infix += 3

scala> infix.toPostfix.foreach(println(_))
1
2
3
*
+

ソースコード

import scala.collection.mutable.Stack

class Infix {
  val numStack = new Stack[Int]()
  val opStack  = new Stack[Char]()
  var postfix = ""
  val Precede  = Map('+'->0,'-'->0,'*'->1,'/'->1)

  def +=(c : Char) {
    if(!opStack.isEmpty && Precede(opStack.top) > Precede(c)){
      numStack += opStack.pop()
      opStack += c
    }else{
      opStack += c
    }
  }

  def +=(n : Int) {
    numStack += n
  }

  def toPostfix() : List[String] = {
    numStack.elements.map(_.toString).toList ++ opStack.elements.map(_.toString).toList.reverse
  }
}

参考