Reverse Polish notation calculator
『すごいHaskellたのしく学ぼう!』 の 10章の逆ポーランド記法電卓を Groovy, Scala, Clojure, Scheme で書いてみる。
Groovy
def solveRPN(expr) { expr.tokenize().inject([]){ acc, v -> "*" == v ? [acc[1] * acc[0], *acc.drop(2)] : "+" == v ? [acc[1] + acc[0], *acc.drop(2)] : "-" == v ? [acc[1] - acc[0], *acc.drop(2)] : [v as double, *acc] }[0] } assert solveRPN("10 4 3 + 2 * -") == -4.0 assert solveRPN("2 3.5 +") == 5.5 assert solveRPN("90 34 12 33 55 66 + * - +") == -3947.0 assert solveRPN("90 34 12 33 55 66 + * - + -") == 4037.0 assert solveRPN("90 3.8 -") == 86.2 assert solveRPN("") == null
0, 1 の順なら pop でも対応できそうだが、1, 0 の順に参照しなければならないので drop と組み合わせた。
意味はないが空文字が渡されたら null を返すようにしてみた。
関連するメソッドの動作。
groovy:000> "".tokenize() ===> [] groovy:000> "".split() ===> [Ljava.lang.String;@83f700d groovy:000> [].head() ERROR java.util.NoSuchElementException: Cannot access first() element from an empty List at groovysh_evaluate.run (groovysh_evaluate:2) ... groovy:000> [][0] ===> null
Scala
val solveRPN: String => Double = _.split(' ').foldLeft(List.empty[Double]){ case (x::y::ys, "*") => (y * x)::ys case (x::y::ys, "+") => (y + x)::ys case (x::y::ys, "-") => (y - x)::ys case (xs, number) => number.toDouble::xs }.head assert( solveRPN("10 4 3 + 2 * -") == -4.0 ) assert( solveRPN("2 3.5 +") == 5.5 ) assert( solveRPN("90 34 12 33 55 66 + * - +") == -3947.0 ) assert( solveRPN("90 34 12 33 55 66 + * - + -") == 4037.0 ) assert( solveRPN("90 3.8 -") == 86.2 )
Scala はパターンマッチがあるので Haskell と変わらない。
14章に Maybe を使った安全版があるので Scala ならそっちを実装するべきだったかもしれない。
空文字にも対応していない。
split が曲者だった。
scala> "".split(' ') res0: Array[String] = Array("") scala> "".split("\\s+") res1: Array[java.lang.String] = Array("") scala> """\s+""".r.split("") res2: Array[String] = Array("") scala> """\S+""".r.findAllIn("") res3: scala.util.matching.Regex.MatchIterator = empty iterator
Clojure
(defn solve-rpn [expr] (defn f [[x y & ys :as s] w] (cond (= "*" w) (cons (* y x) ys) (= "+" w) (cons (+ y x) ys) (= "-" w) (cons (- y x) ys) :else (cons (Double/parseDouble w) s))) (->> expr (re-seq #"\S+") (reduce f []) first)) (assert (= (solve-rpn "10 4 3 + 2 * -") -4.0) ) (assert (= (solve-rpn "2 3.5 +") 5.5) ) (assert (= (solve-rpn "90 34 12 33 55 66 + * - +") -3947.0) ) (assert (= (solve-rpn "90 34 12 33 55 66 + * - + -") 4037.0) ) (assert (= (solve-rpn "90 3.8 -") 86.2) ) (assert (= (solve-rpn "") nil) )
パターンマッチはないが分配束縛があるのでそれを使った。
nil 耐性があるので引数の時点で分配している。
user=> (clojure.string/split "" #"\s+") [""] user=> (re-seq #"\S+" "") nil user=> (first nil) nil user=> (first []) nil
Scheme
(define (solve-rpn expr) (define (f v acc) (cond ((equal? "*" v) (cons (* (cadr acc) (car acc)) (cddr acc))) ((equal? "+" v) (cons (+ (cadr acc) (car acc)) (cddr acc))) ((equal? "-" v) (cons (- (cadr acc) (car acc)) (cddr acc))) (else (cons (string->number v) acc)))) (car (fold f '() (string-split expr #/\s+/)))) (solve-rpn "10 4 3 + 2 * -") ;=> -4 (solve-rpn "2 3.5 +") ;=> 5.5 (solve-rpn "90 34 12 33 55 66 + * - +") ;=> -3947 (solve-rpn "90 34 12 33 55 66 + * - + -") ;=> 4037 (solve-rpn "90 3.8 -") ;=> 86.2 (solve-rpn "") ;=> #f
まだ、どんな関数があるのかよく知らない。
今風な API Doc が欲しい。
gosh> (string-split "" #/\s+/) ("") gosh> (string->number "") #f gosh> (car '()) *** ERROR: pair required, but got () gosh> (use srfi-1) #<undef> gosh> (reduce + 10 '(1 2 3)) 6 gosh> (reduce + 10 '()) 10
終わりに
簡単そうに思えたが書いてみるといろいろ気づくことがあった。
言語によって微妙に違うので注意したい。
2012-06-11 追記
Clojure 版の f はローカル関数にしたつもりだったがグローバルから参照できてしまった。
defn ではなく letfn を使って f を定義するように修正する。
(defn solve-rpn [expr] (letfn [(f [[x y & ys :as s] w] (cond (= "*" w) (cons (* y x) ys) (= "+" w) (cons (+ y x) ys) (= "-" w) (cons (- y x) ys) :else (cons (Double/parseDouble w) s)))] (->> expr (re-seq #"\S+") (reduce f []) first))) (assert (= (solve-rpn "10 4 3 + 2 * -") -4.0) ) (assert (= (solve-rpn "2 3.5 +") 5.5) ) (assert (= (solve-rpn "90 34 12 33 55 66 + * - +") -3947.0) ) (assert (= (solve-rpn "90 34 12 33 55 66 + * - + -") 4037.0) ) (assert (= (solve-rpn "90 3.8 -") 86.2) ) (assert (= (solve-rpn "") nil) )
