Clojure for the Brave and True - infix notation exercise

[Botond Balázs]

Hi,

I'm working through Clojure for the Brave and True and there's a little exercise at the end of Chapter 7:

Create an infix function that takes a list like (1 + 3 * 4 - 5) and transforms it into the lists that Clojure needs in order to correctly evaluate the expression using operator precedence rules.

I ended up implementing the shunting yard algorithm in Clojure to solve it (65 lines, many functions), but I have the suspicion that this exercise isn't meant to be this complicated and that I'm missing a very obvious and elegant solution. What do you think?

Thanks,

Botond

[Jason Felice]

Recursive descent parsers are much smaller for simple cases.  Basically, you write one function per level of precedence, and each tries, greedily, to consume as much as possible for that level of precedence.  e.g.

(defn parse-level1 ;; + and -

  [list]

  ... ; calls parse-level2 repeatedly so long as next operator is + or -

  [l1-expr remaining-tokens])

(defn parse-level2 ;; * and /

  ... ; calls parse-level3 repeatedly so long as next operator is * or /

  [list]

  ...

  [l2-expr remaining-tokens])

(defn parse-level3 ;; numbers

  [list]

  (if (number? list)

    [(first list) (rest list)]))

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Steve Miner]

Not exactly the same problem, but you might like to see an infix implementation from “The Joy of Clojure” by Fogus and Chouser.

http://fogus.me/fun/unfix/infix-src.html

The “Joy” code makes intermediate calculations as it goes. I tweaked it a bit to make a data-reader that only does the infix to prefix transformation. That’s probably closer to what you want.

https://gist.github.com/miner/5224709

Note: the “Joy” code uses vector notation for grouping. You would have to adapt it to use lists.

Here’s the relevant code from my gist, leaving out the data-reader part:

(def && #(and % %2))
(def || #(or % %2))

(def ops '[- + * / < > && || =])
(def rank (zipmap ops (iterate inc 1)))
(def op? rank)

(defn infix
[[a b & [c d e & m]]]
(cond
(vector? a) (recur (list* (infix a) b c d e m))
(vector? c) (recur (list* a b (infix c) d e m))
(op? b) (if (and d (< (rank b 0) (rank d 0)))
(recur (list a b (infix (list* c d e m))))
(recur (list* (list b a c) d e m)))
:else a))

;; example
(infix '[1 + 3 * 4 - 5])
;=> (+ 1 (- (* 3 4) 5))

[Botond Balázs]

Thank you Jason, this is indeed a much nicer solution.

[Botond Balázs]

Thanks miner!