expr.clj

(require '[clojure.contrib.string :as s])

(def precedence {"*" 2 
                 "/" 2 
                 "+" 1 
                 "-" 1})

(def ops {"+" +
          "*" *
          "-" -
          "/" /})

(defn tokens [e] (filter #(not (= "" %)) (s/split #" +" (s/replace-by #"[0-9.]*" #(str " " % " ") e))))
(defn proctok [t rem stack]
 (cond 
    (ops t) (recur (first rem) (rest rem) (concat (list (apply (ops t) (reverse (take 2 stack)))) (drop 2 stack)))
    (nil? t) (first stack)
    t (recur (first rem) (rest rem) (conj stack (read-string t)))))

(defn shunt [e]
 (let [tok (tokens e)]
  (loop [t (first tok) rem (rest tok) out '() stack '()]
    (cond
      (ops t) (let [popped (take-while #(and (ops %1) (<= (precedence t) (precedence %1))) stack)] (recur (first rem) (rest rem) (concat out popped) (concat (list t) (drop (count popped) stack))))
      (= "(" t) (recur (first rem) (rest rem) out (concat (list t) stack))
      (= ")" t) (let [popped (take-while #(not (= "(" %)) stack)] (recur (first rem) (rest rem) (concat out popped) (drop (+ 1 (count popped)) stack)))
      t (recur (first rem) (rest rem) (concat out (list t)) stack)
      (nil? t) (concat out stack)))))

(defn evaluate-postfix [e] (let [t (tokens e)] (proctok (first t) (rest t) '())))
(defn evaluate [e] (let [t (shunt e)] (proctok (first t) (rest t) '())))

;; (evaluate "4+1/(3+2)*2") -> 22/5