Created
May 18, 2020 09:49
-
-
Save ApricotLace/791dd9d0238fccf34d3b09e5035b628d to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ;;3 | blank | |
| ;;3 | + | |
| ;;3 5 | + | |
| ;;3 5 | + * | |
| ;;3 5 10 | + * | |
| ;;3 (* 5 10) | + / | |
| ;;3 (* 5 10) 2 | + / | |
| ;;(+ 3 (/ (* 5 10) 2)) 3 | + | |
| ;;(+ (+ 3 (/ (* 5 10) 2)) 3) | |
| (defn process-numeric-token | |
| "Adds numeric-token to :output vector" | |
| [acc token] | |
| (update acc :output (fn [output] (conj output token)))) | |
| (def operators-precedence { | |
| '+ -1 | |
| '- -1 | |
| '* 1 | |
| '/ 1 | |
| }) | |
| (def not-nil? | |
| (complement nil?)) | |
| (defn build-node | |
| "Creates AST node, e.g. (+ 3 5)" | |
| [operator output] | |
| (let [leaves (reverse (take 2 (reverse output))) | |
| node (concat (list operator) leaves) | |
| popped-output (into [] (drop-last 2 output))] | |
| (conj popped-output node))) | |
| (defn process-remaining-operators | |
| [acc] | |
| (reduce (fn [acc token] | |
| (let [operators (:operators acc) | |
| output (:output acc) | |
| popped-operators (butlast operators) | |
| updated-output (build-node token output)] | |
| {:output updated-output :operators popped-operators})) | |
| acc | |
| (reverse (:operators acc)))) | |
| (defn process-operator-token | |
| "Adds operator-token to :operator vector, or pop operators from it and place them into :output vector" | |
| [acc token] | |
| (loop [acc acc | |
| token token] | |
| (let [token-precedence (token operators-precedence) | |
| operators (:operators acc) | |
| output (:output acc) | |
| operators-top (last operators) | |
| operators-top-precedence (if (not-nil? operators-top) (operators-top operators-precedence))] | |
| (if (and (not-nil? operators-top) (<= token-precedence operators-top-precedence)) | |
| (let [popped-operators (into [] (butlast operators)) | |
| popped-operator (last operators) | |
| updated-output (build-node popped-operator output)] | |
| (recur {:output updated-output | |
| :operators (if (not-nil? popped-operators) | |
| popped-operators | |
| [])} | |
| token)) | |
| (update acc :operators (fn [operators] (conj operators token))))))) | |
| (defn process-tokens-list | |
| "Makes Map from tokens-list e.g. {:output [(+ 5 3) 10 5] :operators [- *]}" | |
| [infix-expression] | |
| (reduce (fn [acc token] | |
| (println acc) | |
| (if (number? token) | |
| (process-numeric-token acc token) | |
| (process-operator-token acc token))) | |
| {:output [] :operators []} | |
| infix-expression)) | |
| (defmacro infix | |
| "Evaluates infix-notation expression, e.g. (5 + 2 - 10)" | |
| [infix-expression] | |
| (-> infix-expression | |
| process-tokens-list | |
| process-remaining-operators | |
| :output | |
| first)) | |
| (infix (3 + 5 * 10 / 2 + 3 / 3)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment