Recursive implementation of Shunting-yard algorithm

gistfile1.clj

(defprotocol parser_p
  (next-type [this token])
  (next-destination [this token last_op])
  (update-out [this dest token])
  (update-op [this dest token])
  (update [this])
  (sort-tokens [this]))

(defrecord Parser [tokens out_stack op_stack operators]
  parser_p
  (next-type [this token]
             (if (number? token)
                 :num
                 :op))
  (next-destination [this token last_op]
                    (case (next-type this token)
                      :op (if (> (last_op operators) ((keyword token) (:operators this)))
                            :pop_op_to_out
                            :op_stack)
                      :num :out))
  (update-out [this dest token]
              (condp = dest
                     :out (conj (:out_stack this) token)
                     :pop_op_to_out (conj (:out_stack this) (last (:op_stack this)) token)
                     (:out_stack this)))
  (update-op [this dest token]
             (condp = dest
                    :pop_op_to_out (vec (butlast (:op_stack this)))
                    :op_stack (conj (:op_stack this) token)
                    (:op_stack this)))
  (update [this]
          (let [token (first (:tokens this))
                dest (next-destination this token (last op_stack))]
            (assoc :out_stack (update-out this dest token) 
                   :op_stack (update-op dest token)
                   :tokens (rest (:tokens this)))))
  (sort-tokens [this]
               (if (empty? (:tokens this))
                 (apply conj (:out_stack this) (reverse (:op_stack this)))
                 (sort-tokens (update this)))))

(defn new-parser [tokens operators]
  (Parser. tokens [] [:none] (merge operators {:none 0})))

(defn parse [tokens operators]
  (sort-tokens (new-parser tokens operators)))

; example:
; (parse [2 :+ 3 :* 4 :+ 5] {:+ 1 :* 2})
; => [2 3 4 :* :+ 5 :+ :none]