Clojure 平面序列到树中

Question

我有以下向量，[-1 1 2 -1 3 0 -1 2 -1 4 0 3 0 0]

代表树[[1 2 [3] [2 [4] 3]]]

其中 -1 开始一个新分支，0 结束它。如何将原始向量转换为可用的树状 clojure 结构（嵌套向量、嵌套映射）？我认为 clojure.zip/zipper 可以做到，但我不确定如何构建这些函数参数。

Answer 1

不知怎的，这感觉像是在作弊：

[(read-string
  (clojure.string/join " "
                       (replace {-1 "[" 0 "]"}
                                [-1 1 2 -1 3 0 -1 2 -1 4 0 3 0 0])))]

Answer 2

拉链是一个很好的工具：

(require '[clojure.zip :as zip])

(def in [-1 1 2 -1 3 0 -1 2 -1 4 0 3 0 0])
(def out [[1 2 [3] [2 [4] 3]]])

(defn deepen [steps]
  (->> steps
       (reduce (fn [loc step]
                 (case step
                   -1 (-> loc
                          (zip/append-child [])
                          (zip/down)
                          (zip/rightmost))
                   0 (zip/up loc)
                   (zip/append-child loc step)))
         (zip/vector-zip []))
       (zip/root)))

(assert (= (deepen in) out))

Answer 3

这对于一些递归来说并不难：

(defn numbers->tree [xs]
  (letfn [(step [xs]
            (loop [ret [], remainder xs]
              (if (empty? remainder)
                [ret remainder]
                (let [x (first remainder)]
                  (case x
                    0 [ret (next remainder)]
                    -1 (let [[ret' remainder'] (step (next remainder))]
                         (recur (conj ret ret'), remainder'))
                    (recur (conj ret x) (next remainder)))))))]
    (first (step xs))))

想法是有一个函数 (step) 可以找到一个子树，returns 那棵树以及还有哪些数字需要处理。它对大多数输入进行迭代（通过 loop），并在遇到 -1 时启动自身的递归实例。唯一棘手的部分是确保使用从这些递归调用返回的 remainder，而不是继续处理您位于其中的列表。

Clojure 平面序列到树中

Clojure flat sequence into tree

tree

clojure

zipper