infix.clj

(defn ^:private encase-single-op
  "Puts a single matching target operation in parentheses"
  [expression target-op?]
  ;; no need to do something if it's already a simple expression
  (if (= 3 (count expression))
    expression
    (loop [prev []
           [a op b & more] expression]
      (cond
        (target-op? op)
        (concat prev [(list a op b)] more)
        (nil? more)
        expression
        :else
        (recur (conj prev a op) (conj more b))))))


(defn ^:private encase-target-ops
  "Puts all matching target operations in parentheses"
  [expression target-op?]
  ;; check if we need to do something
  (loop [exp expression]
    (let [new-exp (encase-single-op exp target-op?)]
      (if (= exp new-exp)
        exp
        (recur new-exp)))))


(def ^:private priorities '{+ 1, - 1, * 2, / 2})

;; sets of same-prio-operators in descending priority order
(def ^:private op-sets-ordered-by-prio (->> priorities
                                            (sort-by val)
                                            reverse
                                            (partition-by val)
                                            (map (comp set #(map key %)))))

(def ^:private unknown-op? (-> priorities keys set complement))


(defn ^:private prioritize
  "Takes an infix expression of any length and puts sub-expressions in parentheses
  according to their operator precedences."
  [expression]
  (reduce
    encase-target-ops
    expression
    (cons unknown-op? op-sets-ordered-by-prio)))          ;; unknown operators get the highest priority


(defn infix->prefix
  "Takes a single form with calculations in infix notation and converts it to prefix notation."
  [expression]
  (let [[a op b] (prioritize expression)]
    (list op
          (if (seq? a) (infix->prefix a) a)
          (if (seq? b) (infix->prefix b) b))))


(defmacro infix
  "Runs a given form containing a calculation in infix notation."
  [form]
  (infix->prefix form))