clojure replace operator with its answer

Question

I am trying to produce a function which takes the expression 'tree' as its argument and returns the tree with the relevant calculated values in place of the operators.

An example of what a tree could look like is:

(* (+ 10 (* 4 9)) (- 6 10))

And the function should return:

(-184 (46 10 (36 4 9)) (-4 6 10))

If anyone could provide me a solution or two and explain how they work to point me in the right direction, that would be great.

(def a '(* (+ 5 (* 3 7)) (- 6 8)) )

(defn evaltree [tree] (cons (eval (first (rest tree))) tree)) 

is all I have so far. It evals the first part of the list, but doesn't recurse through to do the rest of the list and doesn't replace the operator, it only adds the value to the beginning.

Answer 1

The functions in clojure.walk are useful when you want to update arbitrary nested data structures, the following solution seems to work for this case.

(require '[clojure.walk :as w])

(defn op->answer [expr]
    (if (list? expr)
      (cons (eval expr) (rest expr))
      expr))

(w/prewalk op->answer '(* (+ 10 (* 4 9)) (- 6 10)))

;;=> (-184 (46 10 (36 4 9)) (-4 6 10))

clojore.walk/prewalk does a pre-order traversal of the expression tree and replaces each node with the return value from your function. You can see the order or calls with the following snippet.

(w/prewalk #(do (println %) %) '(* (+ 10 (* 4 9)) (- 6 10)))

;; => prints the following 
(* (+ 10 (* 4 9)) (- 6 10))
*
(+ 10 (* 4 9))
+
10
(* 4 9)
*
4
9
(- 6 10)
-
6
10

Answer 2

Ain't that hard: As usual with such evaluators you have two cases you need to distinguish: Self evaluating values and calls (function application).

(defn evaluate
  [expression]
  (if (seq? expression) ;any sequence is a call with the operator in the first position
    (evaluate-call expression)
    expression))

Evaluating a call is done by first evaluating the operands/arguments. If one of these is a call by itself, then we'll get a sequence back. In the first position of this sequence will be - by induction - the result of the expression (since it's already evaluated).

(defn evaluate-call
  [expression]
  (let [arguments (map evaluate (rest expression))] ; evaluate arguments
    (cons (apply (get *functions* (first expression)) ; get function to apply
                 (map #(if (seq? %) (first %) %) arguments)) ; extract result from evaluated result, if neccessary
          arguments)))

Finally, we pack up our result into a sequence, together with the (evaluated) arguments (this is what the cons does).

Of course, we also need to define our available functions somewhere:

(def ^:dynamic *functions*
  {'+ +
   '- -
   '* *
   '/ /})

Running this code in CIDER (sorry, can't get ideone to work with clojure code) gives me:

evaluating.core> (evaluate '(* (+ 10 (* 4 9)) (- 6 10)))
;;=> (-184 (46 10 (36 4 9)) (-4 6 10))