448 PurelyFunctional.tv Newsletter

00 Reverse-Polish calculator.md

Reverse-Polish calculator

Reverse-Polish notation is a way to write mathematical expressions where the operator appears after the operands. For example:

1 2 +      => 1 + 2 = 3

In traditional parenthetical notation, that is equivalent to (1 + 2) and in Lisp (+ 1 2). If we assume there are four binary arithmetic operators (+, -, *, and /), we can write arbitrarily complex expressions with no need for parentheses.

Examples

1 2 + 3 +   => (1 + 2) + 3 = 6
4 2 * 2 2 + + 8 / => ((4 * 2) + (2 + 2)) / 8 = 2

Your job is to take a string of numbers and operators (all separated by spaces), parse them, and calculate the answer.

Examples

(rpol "1") ;=> 1
(rpol "1 2 +") ;=> 3
(rpol "1 2 + 3 +") ;=> 6
(rpol "4 2 * 2 2 + + 8 /") ;=> 2

Notes

• All operations are binary.
• There are some cases where there aren't enough arguments. You should throw an exception.
• There are some cases where there are too many arguments. Return the result of the last operation performed.

Hint

• Use a stack.

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn interpret [dst x]
  (if (symbol? x)
    (let [[b a & r] dst]
      (conj r ((eval x) a b)))
    (conj dst x)))

(defn rpol [input]
  (->> (clojure.string/split input #"\s+")
       (transduce (map read-string) (completing interpret) '())
       first))

(defn rpol [s]
  (let [ops {"*" * "/" / "+" + "-" -}]
    (last (reduce (fn [a v]
            (if (contains? ops v)
              [(reduce (get ops v) a)]
              (conj a (int v))))
          [] (clojure.string/split s " ")))))

(require '[clojure.test :refer [deftest is]])
(require '[clojure.string :as str])
(require '[clojure.edn :as edn])

(defn- stack-eval [stack obj]
  (cond
    (number? obj)
    (cons obj stack)

    (#{'+ '- '* '/} obj)
    (let [[b a & rst] stack]
      (cons ((eval obj) a b) rst))

    :else stack))

(defn rpol [input]
  (->> (str/split input #"\s+")
       (map edn/read-string)
       (reduce stack-eval nil)
       last))

(deftest rpol-test
  (is (= 1 (rpol "1")))
  (is (= 3 (rpol "1 2 +")))
  (is (= 6 (rpol "1 2 + 3 +")))
  (is (= 1 (rpol "2 3 * 1 - 5 /")))
  (is (= 3/2 (rpol "4 2 * 2 2 + + 8 /")))
  (is (= 2 (rpol "1 1 + 10")))
  (is (thrown? Exception (rpol "1 +"))))

(require '[clojure.string :as str])

(defn rpol [s]
  (->> (str/split s #" ")
       (reduce #(if-let [f ({"*" * "/" / "+" + "-" -} %2)]
                 (conj (pop (pop %))
                       (f (peek (pop %)) (peek %)))
                 (conj % (Long/parseLong %2))) [])
       first))

(defn rpol [s]
  (transduce (map clojure.edn/read-string)
             (fn ([stack x]
                  (if (symbol? x)
                    (let [op2 (peek stack)
                          stack (pop stack)
                          op1 (peek stack)
                          stack (pop stack)]
                      (conj stack ((ns-resolve *ns* x) op1 op2)))
                    (conj stack x)))
               ([stack] (peek stack)))
             nil
             (clojure.string/split s #" +")))

(require 'clojure.string)

(defn- step [stack x]
 (if-let [op ({"+" + "-" - "*" * "/" /} x)]
         (conj (pop (pop stack)) (op (peek (pop stack)) (peek stack)))
         (conj stack (Long/parseLong x))))

(defn rpol [str]
 (first (reduce step '() (clojure.string/split str #"\s+"))))

(defn tokens [s]
  (->> (clojure.string/split s #"\s+")
       (map (fn [tok]
              (or ({"+" + "-" - "*" * "/" /} tok)
                  (Integer/parseInt tok))))))

(defn pop2 [input-stack op]
  (->> [:arg2 :arg1] 
       (reduce (fn [[stack args] _]
                 (if (not (peek stack))
                   (throw (Exception. 
                           (str "Missing argument for binary operator: " op
                                " in argument list: " input-stack)))
                   [(pop stack) (conj args (peek stack))]))
               [input-stack ()])))

(defn rpol [syms-str]
  (->> syms-str tokens
       (reduce (fn [stack arg-or-op]
                 (if (fn? arg-or-op)
                   (let [[stack' args] (pop2 stack arg-or-op)]
                        (conj stack' (apply arg-or-op args)))
                   (conj stack arg-or-op)))
               [])
       ((fn [res]
          (if (< 1 (count res))
            (throw (Exception. (str "Incomplete result - missing operator: "
                                    res)))
            (peek res))))))

(rpol "1") ;=> 1
(rpol "1 2 +") ;=> 3
(rpol "1 2 + 3 +") ;=> 6
(rpol "4 2 * 2 2 + + 8 /") ;=> 3/2

(require '[clojure.test :refer [deftest is]])
(deftest rpol-throws-test
  (is (thrown-with-msg? Exception #".*missing operator.*" (rpol "4 2 + 3")))
  (is (thrown-with-msg? Exception #"Missing argument.*" (rpol "1 +"))))