Skip to content

Instantly share code, notes, and snippets.

@NPException
Last active September 22, 2021 15:32
Show Gist options
  • Save NPException/1e5538797508be1150619c270724a084 to your computer and use it in GitHub Desktop.
Save NPException/1e5538797508be1150619c270724a084 to your computer and use it in GitHub Desktop.
(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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment