PhillyDev Slack #daily_programmer 2017-08-30 - Reverse Polish Notation

rpn.clj

(ns daily.rpn
  ;; Needs [instaparse "1.4.7"] in project deps
  (:require [instaparse.core :as insta]
            [instaparse.failure :as failure]
            [clojure.string :as string]
            [clojure.edn :as edn]))

(def whitespace
  (insta/parser
   "whitespace = #'\\s*'"))

(def grammar
  "expression = term | expression (plus | minus) term
   term       = factor | expression (times | div) factor
   <factor>   = number | ( <'('> expression <')'> )
   plus       = '+'
   minus      = '-' | '−'
   times      = '*' | '×' | 'x'
   div        = '/' | '÷'
   number =     #'\\d+'
   ")

(def parse
  (insta/parser grammar :auto-whitespace whitespace))

(defn process [parse-tree]
  (->> parse-tree
       (insta/transform
        {:expression (fn [a & [op b]] (if op [a b op] a))
         :term       (fn [a & [op b]] (if op [a b op] a))
         :plus       (constantly '+)
         :minus      (constantly '-)
         :times      (constantly '*)
         :div        (constantly '/)
         :number     edn/read-string})))

(defn infix->rpn [expr]
  (let [parse-tree (parse expr)]
    (if (insta/failure? parse-tree)
      (failure/print-reason parse-tree)
      (->> parse-tree process flatten (map str) (string/join " ")))))