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

拉鍊是一個很好的工具： 

(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 2

不知怎的，這感覺就像作弊：

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

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），找到一個子樹，並返回th在樹上還有哪些數字需要處理。它通過迭代（通過loop）進行大部分輸入，並在運行到-1時啓動它自己的遞歸實例。唯一棘手的部分是確保使用從這些遞歸調用返回的remainder，而不是繼續處理中間的列表。