parsing program for nested parens and square brackets
Mark Volkmann
http://dibblego.wordpress.com/2008/09/05/haskell-scala-java-7-functional-java-java/#comment-2460.
It's a parsing problem for which he compares solutions in Haskell,
Scala and Java. I added a Clojure solution. I don't know if this is
the "best" way to solve this with Clojure, but it certainly works.
Here's my code, including unit tests.
(use 'clojure.test)
(defn- match [prev-char next-char]
(condp = prev-char
\( (= next-char \))
\[ (= next-char \])
false))
; Need a better name for this function.
(defn- helper [s stack]
(if (empty? s)
(empty? stack)
(let [c (first s)
top (first stack)
stack (if (match top c) (next stack) (cons c stack))]
(helper (next s) stack))))
(defn balanced? [s] (helper s '()))
(doseq [arg *command-line-args*]
(println (balanced? arg)))
(deftest match-test
(is (match \( \)))
(is (match \[ \]))
(is (not (match \( \{))))
(deftest balanced-test
(is (balanced? "()"))
(is (balanced? "[]"))
(is (balanced? "([])"))
(is (balanced? "[()]"))
(is (balanced? "[]()"))
(is (balanced? "[][[([])]]"))
(is (not (balanced? "(")))
(is (not (balanced? ")")))
(is (not (balanced? "[")))
(is (not (balanced? "]")))
(is (not (balanced? "][")))
(is (not (balanced? ")(")))
(is (not (balanced? "( )")))
(is (not (balanced? "([)")))
(is (not (balanced? "[)]")))
(is (not (balanced? "([)]")))
(is (not (balanced? "({})")))
(is (not (balanced? "[())]"))))
(run-tests)
--
R. Mark Volkmann
Object Computing, Inc.
Stuart Halloway
The balanced-test would be a great place to use "are" instead of "is".
Cheers,
Stu
Laurent PETIT
I think you could use recur instead of the direct recursive call,
Regards,
--
Laurent
2009/7/2 Mark Volkmann <r.mark....@gmail.com>:
Mark Volkmann
Halloway<stuart....@gmail.com> wrote:
>
> Hi Mark,
>
> The balanced-test would be a great place to use "are" instead of "is".
(deftest balanced-test
(are [text result]
(= (balanced? text) result)
"()" true
"[]" true
"([])" true
"[()]" true
"[]()" true
"[][[([])]]" true
"(" false
")" false
"[" false
"]" false
"][" false
")(" false
"( )" false
"([)" false
"[)]" false
"([)]" false
"({})" false
"[())]") false)
Mark Volkmann
>
> Hi,
>
> I think you could use recur instead of the direct recursive call,
Great idea! Simply changing "helper" to "recur" works.
Laurent PETIT
convey the semantics of using the cons list as a stack.
As far as performance is on the table, I'm not sure whether of
cons'ing over lists or conj'ing over vectors would have the better
performance (maybe it's just comparable ! :-)
2009/7/2 Mark Volkmann <r.mark....@gmail.com>:
Mark Volkmann
>
> There are also peek and pop functions in core that you could you to
> convey the semantics of using the cons list as a stack.
Yes, that's a nice improvement! Here's the new code without the tests
which didn't change. Now it is using a vector instead of a list. Too
bad there is no push function in core. I'm using conj.
(defn- match [prev-char next-char]
(condp = prev-char
\( (= next-char \))
\[ (= next-char \])
false))
(defn- balanced-helper [s stack]
(if (empty? s)
(empty? stack)
(let [c (first s)
top (peek stack)
stack (if (match top c) (pop stack) (conj stack c))]
(recur (next s) stack))))
(defn balanced? [s] (balanced-helper s []))
(doseq [arg *command-line-args*]
(println (balanced? arg)))
> As far as performance is on the table, I'm not sure whether of
> cons'ing over lists or conj'ing over vectors would have the better
> performance (maybe it's just comparable ! :-)
--
Stephen C. Gilardi
On Jul 2, 2009, at 3:21 PM, Mark Volkmann wrote:
> Now it is using a vector instead of a list. Too
> bad there is no push function in core. I'm using conj.
conj is the correct thing to use for the push operation.
Here's my take on it based on yours. This bails early as soon as there
is a mismatch or an illegal character:
(ns challenge
(:use clojure.test))
(def lefts #{\( \[})
(def matches {\( \) \[ \]})
(defn balanced? [s]
(loop [s s stack ()]
(if (seq s)
(let [[c & s] s]
(if (lefts c)
(recur s (conj stack c))
(if (= (matches (peek stack)) c)
(recur s (pop stack))
false)))
(empty? stack))))
(deftest balanced-test
(are [text result]
(= (balanced? text) result)
"()" true
"[]" true
"([])" true
"[()]" true
"[]()" true
"[][[([])]]" true
"(" false
")" false
"[" false
"]" false
"][" false
")(" false
"( )" false
"([)" false
"[)]" false
"([)]" false
"({})" false
"[())]") false)
(defn main []
(run-tests 'challenge))
--Steve
Mark Volkmann
>
> On Jul 2, 2009, at 3:21 PM, Mark Volkmann wrote:
>
>> Now it is using a vector instead of a list. Too
>> bad there is no push function in core. I'm using conj.
>
> conj is the correct thing to use for the push operation.
Right, but the point Laurent was making is that using peek and pop are
good because they convey the fact that I'm using a vector as a stack.
For that reason it would be nice if there was a push function to go
along with peek and pop.
> Here's my take on it based on yours. This bails early as soon as there is a
> mismatch or an illegal character:
Yeah, I realized mine wasn't doing that, but was happy that it gave
the correct result anyway since the illegal characters get added to
the stack and are never popped off. Your implementation is certainly
more efficient though.
> (ns challenge
> (:use clojure.test))
>
> (def lefts #{\( \[})
> (def matches {\( \) \[ \]})
Cool use of a set and a map!
> (defn balanced? [s]
> (loop [s s stack ()]
> (if (seq s)
Interesting use of seq.
(empty? s) seems more clear to me though.
> (let [[c & s] s]
> (if (lefts c)
> (recur s (conj stack c))
> (if (= (matches (peek stack)) c)
> (recur s (pop stack))
> false)))
> (empty? stack))))
>
> (defn main []
> (run-tests 'challenge))
Very nice! Thanks for sharing!
Laurent PETIT
OK, so here's my attempt at doing this the most higher order but also
the most understandable I could do.
Hope you enjoy reading it as much as I enjoyed polishing it :-) :
;; from command line:
;; java -cp clojure.jar /path/to/challenge.clj "()" "((([[]])))" ... ...
(ns challenge)
(def push conj)
(def closing-counterpart { \( \), \[ \] })
(def opening-char? closing-counterpart)
(defn matching-pair? [left right] (= right (closing-counterpart left)))
(defn consume-one [stack c]
(if (or (opening-char? c)
(not (matching-pair? (peek stack) c)))
(push stack c)
(pop stack)))
(defn balanced? [s]
(empty? (reduce consume-one [] s)))
(defn main []
(apply print (map balanced? *command-line-args*)))
(when *command-line-args*
(main))
It's the second time I wish I had a version of reduce that allows to
quit the reduction early.
This version of reduce would allow to quit early, just like the
solution provided by Steven.
But maybe it just there's something wrong with me ! :-)
Say I have this function, which takes a keyword option at the end of
the form :quick-exit <quick-exit-val>
then I could write (reduce consume-one [] s :quick-exit nil) instead
of (reduce consume-one [] s),
and consume-one could be shortened to (notice the use of cond
automatically returning nil if nothing matches, instead of having
explicitly to return (push stack c) to continue consuming the string
(as in Mark's solution) :
(defn consume-one [stack c]
(cond
(opening-char? c) (push stack c)
(matching-pair? (peek stack) c) (pop stack)))
2009/7/2 Mark Volkmann <r.mark....@gmail.com>:
Mark Tarver
(define test-brackets
X -> (not (= (compile <paren> (COERCE X LIST)) fail!)))
(defcc <paren>
#\[ <paren> #\] <paren>;
#\( <paren> #\) <paren>;
<token> <paren>;
<e> := [];)
(defcc <token>
-*- := (if (element? -*- [#\[ #\] #\( #\)]) #\Escape -*-);)
Testing
(5-) (test-brackets "()")
true
(6-) (test-brackets "())")
false
(7-) (test-brackets "([))]")
false
(8-) (test-brackets "([])")
true
(9-) (test-brackets "([)]")
false
(10-) (test-brackets "[][[([])]]")
true
Mark
Mark Tarver
(define test-brackets
X -> (not (= (compile <paren> (COERCE X LIST)) fail!)))
(defcc <paren>
#\[ <paren> #\] <paren>;
#\( <paren> #\) <paren>;
<token> <paren>;
<e> := [];)
(defcc <token>
-*- := (if (element? -*- [#\[ #\] #\( #\)]) #\Escape -*-);)
Laurent PETIT
;; using just clojure 1.0.0 without any additional library :-)
;; from command line:
;; java -cp clojure.jar /path/to/challenge2.clj "()" "((([[]])))" ... ...
(ns challenge2)
(defn balanced? [s]
(and
(every? #{ \( \) \[ \] } s)
(try (read-string s) true (catch java.lang.RuntimeException e false))))
(defn main [] (apply print (map balanced? *command-line-args*)))
(when *command-line-args* (main))
--
laurent
2009/7/2 Mark Volkmann <r.mark....@gmail.com>:
B Smith-Mannschott
>
> Hey, how come we did not see this even more concise version sooner ? :-):
>
> ;; using just clojure 1.0.0 without any additional library :-)
> ;; from command line:
> ;; java -cp clojure.jar /path/to/challenge2.clj "()" "((([[]])))" ... ...
> (ns challenge2)
>
> (defn balanced? [s]
> (and
> (every? #{ \( \) \[ \] } s)
> (try (read-string s) true (catch java.lang.RuntimeException e false))))
>
> (defn main [] (apply print (map balanced? *command-line-args*)))
>
> (when *command-line-args* (main))
>
> Hehe
ROFL. :-D
Brilliantly punny solution.
// Ben
Christophe Grand
(def push conj)
(def closing-counterpart { \( \), \[ \] })
(def opening-char? closing-counterpart)
(defn matching-pair? [left right] (= right (closing-counterpart left)))
(defn consume-one [stack c]
(if (or (opening-char? c)
(not (matching-pair? (peek stack) c)))
(push stack c)
(pop stack)))
(defn balanced? [s]
(empty? (reduce consume-one [] s)))
(defn main []
(apply print (map balanced? *command-line-args*)))
(when *command-line-args*
(main))
I think you don't need opening-char?
(defn balanced? [s]
(let [tr {\( \) \[ \]}]
(empty?
(reduce #(if (= (peek %1) %2)
(pop %1)
(conj %1 (tr %2))) [] s))))
I push "transposed" characters on the stack, thus only \] \) or nil can be on the stack.
Since nil isn't equal to a character, it will never be popped and thus it ensures the stack will not be empty.
It's the second time I wish I had a version of reduce that allows to
quit the reduction early.
--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.blogspot.com/ (en)
Laurent PETIT
Indeed, not easy to be general, concise and elegant at the same time here ...
What about:
"(reduce-until pred reductor init-acc coll)" ?
pred would be a function of acc (the accumulator) and i (next item from coll),
be executed before reductor,
and return
* nil or false for continuing,
* a vector with a specific return value (which could be acc or something else)
* special meaning keyword :next for reduce-until to return the final
call of reductor on acc and i (this one could be got rid of, though ?)
e.g. :
my version would become
(defn consume-one [stack c]
(cond
(opening-char? c) (push stack c)
(matching-pair? (peek stack) c) (pop stack)))
(defn balanced? [s]
(empty? (reduce-until #(when-not (consume-one %1 %2) [[:error]])
consume-one [] s)))
or yours:
(defn balanced? [s]
(let [tr {\( \) \[ \]}]
(empty?
(reduce-until (fn [acc v] (when (nil? (get acc 0 true)) [acc]))
#(if (= (peek %1) %2)
(pop %1)
(conj %1 (tr %2))) [] s))))
But all in all I don't find this is much a readability or
composability improvement ..., or is this ?
Regards,
--
Laurent
carlitos
Probably the following is much less efficient than the other solutions
proposed, but I find it easier to understand (and if I didn't
misunderstand the problem it gives the right answer).
(defn simplify-1
"remove adjacent pairs of opening/closing brackets"
([string] (simplify-1 "" string))
([prefix [a & [b & cdef :as bcdef]]]
(cond (nil? a) prefix
(#{"()" "[]"} (str a b)) (recur prefix cdef)
:otherwise (recur (str prefix a) bcdef))))
(defn simplify [s]
(let [ss (simplify-1 s)]
(if (= ss s) ss (recur ss))))
(defn balanced? [s]
(empty? (simplify s)))
Cheers,
Carlos
Russell Christopher
(def matches {\( \) \[ \]})
(empty? (reduce #(if (= (matches (peek %1)) %2) (pop %1) (conj %1 %2)) [] s)))
Learning Clojure. So far I'm really liking it. This is the first time I've tried anything outside of some REPL incantations from books, blogs, this list, etc thus it wouldn't be a total surprise if it's not idiomatic or correct in some way. It does seem to work although it could be more efficient if it could bail earlier on some of the false strings