Mittwoch, 6. Juni 2012

Reverse Polish Notation in Clojure

Nachdem ein Kollege von mir mal die Reverse Polish Notation (zu deutsch: Umgekehrte Polnische Notation) in Scala implementiert hatte (Link zum Blogeintrag), wollte ich die selbe Aufgabenstellung in Clojure l?sen. Der erste Versuch sah ungefähr so aus:
(ns rpn.core
  (:use [clojure.contrib.string :only (split)]))

(def *operations* {"+" +
                   "-" -
                   "*" *
                   "/" /})

(defn parse-strings [list]
  (map (fn [x] (if (re-find #"^\\d+$" x)
                 (Double/parseDouble x)
                 (*operations* x)))
       list))

(defn rpn [x]
  (let [y (parse-strings (split #"\\s" x))]
    (loop [stack ''()
           rest-of-input y]
      (if (and (= 1 (count stack)) (empty? rest-of-input))
        (first stack)
        (let [next-value (first rest-of-input)]
          (if (number? next-value)
            (recur (conj stack next-value)
                   (rest rest-of-input))
            (recur (conj (nthnext stack 2)
                         (next-value (nth stack 1) (nth stack 0)))
                   (rest rest-of-input))))))))
Da ich länger nichts mehr in Clojure getan hatte, brauchte diese Lösung erstmal seine Zeit und zudem finde ich persönlich diese Lösung irgendwie nicht schön. Aufgrund dessen habe ich mich nochmals dran gesetzt und versucht eine andere Lösung zu finden. Heraus kam das hier:
(ns rpn.core
  (:use [clojure.contrib.string :only (split)]))

(def *operations* {"+" +
                   "-" -
                   "*" *
                   "/" /})

(defn parse-strings [list]
  (map (fn [x] (if (re-find #"^\\d+$" x)
                 (Double/parseDouble x)
                 (*operations* x)))
       list))

(defn rpn [input]
  (reduce (fn [stack op]
            (if (number? op)
              (conj stack op)
              (let [[r l & rest-of-stack] (reverse stack)]
                (conj rest-of-stack (op l r)))))
          []
          (parse-strings (split #"\\s" input))))

Keine Kommentare:

Kommentar veröffentlichen