Determine if braces in a string are balanced in Clojure

Question

I'm currently learning Clojure, and am working through a few exercises. The exercise that I'm working on right now is accept an arbitrary string and determine if the opening and closing parenthesis, curly brackets, and square brackets correctly nest and line up to each other.

For example, "hello { ( world ) } []" would be an example of a balanced string whereas "foo { [ bar ) [}" would be an example of an unbalanced string.

While I have previous experience in other programming languages like Python and Java, I'm very new to Clojure and functional languages in general, so am uncertain if my code is fully idiomatic or if there's a more cleaner or efficient way to complete the problem.

Here's what I have so far. The approach I've taken is to first filter out any characters that are not opening or closing braces. I then loop through the characters, adding the opening brackets to a stack and checking closing brackets against the stack to see if it matches.

Any feedback would be greatly appreciated.

; Given a N different open and close braces in a string ""( { [ } ] )"". 
; Write a program to check to see if the braces in the string are balanced.

(ns braces
  (:require [clojure.string :as str]))

(def braces #{\( \) \[ \] \{ \}})

(def pairs { \) \(,
             \] \[,
             \} \{ })

(defn remove-non-braces
  "Takes a string and removes any characters that is not a brace."
  [raw-string]
  (filter #(braces %) raw-string))

(defn is-balanced?
  "Returns true if all the braces in the string are balanced; returns false otherwise."
  ([raw-string] (is-balanced? (remove-non-braces raw-string) []))
  ([string stack]
    (let [[first-char & other] string]
      (cond
        ; if we're done, but the stack is non-empty, we still have opening braces left.
        (empty? string) (empty? stack)
        ; if we encounter a closing brace, check it against the top of the stack.
        (pairs first-char) (if (= (pairs first-char) (peek stack))
                               (is-balanced? other (pop stack))
                               false)
        ; if we encounter an opening brace, add it to the stack.
        :else (is-balanced? other (conj stack first-char))))))

(defn test-strings
  "Tests the given strings and prints the results."
  [& strings]
  (let [format-str (fn [s] (str (is-balanced? s) " : " s))]
    (println (str/join "\n" (map format-str strings)))))

(defn main
  "The main entry point of the program."
  []
  (println "SHOULD PASS")
  (test-strings
    "Hello { ( world ) } [] end"
    ""
    "{[] () {[{{ }}]} ([{}])}")
  (println "")
  (println "SHOULD FAIL")
  (test-strings
    "Hello { world"
    "{{"
    "])"
    "}}{{"
    "{[))"))

(main)

Answer 1

Recursion

Use recur to do tail-call recursion:

Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler.

Destructuring

You can use :as to avoid the unnecessary let here:

  ([string stack]
    (let [[first-char & other] string]

Instead:

 ([[first-char & other :as string] stack]

Repeated Constants

Here you are entering the same data by hand twice:

(def braces #{\( \) \[ \] \{ \}})

(def pairs { \) \(,
             \] \[,
             \} \{ })

Instead you can do:

(def braces (set (concat (keys pairs) (vals pairs))))

Testing

Use clojure.test to do unit testing. It does have a standard and useful failure reporting. You needn't write a test harness like test-strings yourself. You should only report failures, because test are only useful when they are reporting failures. Most your test should be passing at any time, so any relevant information (a failing test case) should not be lost in noise (dozens of lines of "test-case-xyz passed just as the 937 time before").

Make a habit of putting test code in a separate namespace that does depend on the code tested, but not vice-versa.

After requiring clojure.test:

... (:require [clojure.test :refer :all] ...

You define tests like this:

(deftest non-braces-ignored
  (is (is-balanced? "Hello { ( world ) } [] end")))

(deftest empty-string-is-brace-balanced
  (is (is-balanced? "")))

(deftest some-long-balanced-string
  (is (is-balanced? "{[] () {[{{ }}]} ([{}])}")))

You can group several of similar tests like this until you can find a descriptive name for them, although failure message is not as useful as above tests:

(deftest examples-of-non-balanced-strings
  (are [x] (not (is-balanced? x))
       "Hello { world"
       "{{"
       "])"
       "}}{{"
       "{[))"))

and run these tests like this:

(run-tests)

Namespaces

Don't put function calls inside a namespace. Reloading a namespace should be idempotent. Also if the function call is something like (main) you don't gain much; however if you are calling some non-trivial initialization code then it deserves it own function.