shunt.clj

(ns src.core)

(def regex #"(\d+(?:\.\d+)?)|([().^*\/+-])")

(def presedence {'+ 1
                 '- 1
                 '* 2
                 '/ 2})

(defn tokenize [expr]
  (let [matches (re-seq regex expr)]
    (map first matches)))

(defn shunt* [{:keys [queue stack] :as m} t]
  (cond (= "(" t)
        (update m :stack conj "(")

        (= ")" t)
        (-> m
            (update :queue into (take-while (partial not= "(") stack))
            (assoc :stack (rest (drop-while (partial not= "(") stack))))
        :else
        (let [v (read-string t)]
          (cond
            (number? v)
            (update m :queue conj v)

            (< (presedence v) (presedence (peek stack) -1))
            (-> m
                (update :queue into stack)
                (assoc :stack (list v)))

        :else
        (update m :stack conj v)))))

(defn shunt [tokens]
  (let [{:keys [queue stack] :as state} (reduce shunt* {:queue []
                                                        :stack '()} tokens)]
    (into queue stack)))

(defn calculate [queue]
  (reduce (fn [stack s]
            (if (number? s)
              (conj stack s)
              (let [fst (first stack)
                    snd (second stack)
                    result (eval (list s snd fst))]
                (conj (rest (rest stack)) result)))) '() queue))

(->> "(5 + 3) * (4 - 3) - 1 * 5"
     (tokenize)
     (shunt)
     (calculate))