反序列化广度优先树

Question

我需要四树的工作方式如下：

 
      p 
     /| |\ 
     /| | \  
    /| | \ 
     p w b p 
    /| |\  /| |\ 
/| | \ /| | \ 
    b w w b w b w b 

但他们一直在使用广度优先的顺序序列化到一个字符串，所以以前的树将有以下表现：

ppwbpbwwbwbwb

我想这样的字符串转换为嵌套向量结构：

[ [ b w w b ] w b [ w b w b] ]用于添加复杂的例子

(defn read-quad-tree [pattern] 
    (loop [r     [] 
     [s & rs :as stack] [] 
     [p & rp :as pending] (reverse pattern)] 
    (cond (nil? pending) (first r) 
      (= (count r) 4) (recur [] (conj stack (reverse r)) pending) 
      (= p \p)  (recur (conj r s) rs rp) 
      :else   (recur (conj r p) stack rp)))) 

被修改：

但有时下面的代码不能正常工作

另一个（失败）的例子。接下来的树：

 
        | 
     +------+-------+------+ 
     |  |  |  | 
     |  w  w  | 
     |      | 
    +---+---+---+   +---+---+---+ 
    | | | |   | | | | 
    | w w |   | w w | 
    |   |   |   | 
+-+-+-+  +-+-+-+ +-+-+-+  +-+-+-+ 
| | | |  | | | | | | | |  | | | | 
b b b b  w w w w b b w w  b w b w 

将被序列化为：

ppwwppwwppwwpbbbbwwwwbbwwbwbw

和目标是获得以下结构：

[ [ [ b b b b ] w w [ w w w w ] ] w w [ [ b b w w ] w w [ b w b w ] ] ]

但我的代码给出了不同的（错误）结构。

Answer 1

您的代码患有代表列表而不是（预期）向量的名称。

这已经可以从函数的返回值看出来了，这是一个列表。

看代码的这些部分：

(loop ... 
     [s & rs :as stack] 
     ... 
     (recur (conj r s) rs rp) 

高亮[s & rs :as stack]将得到堆栈载体，名字的第一个元素小号，其余元素为列表RS（！）。由于rs是一个列表，它会在某些时候像栈（通过最后的recur）那样传递，然后它也是一个列表，而不是一个向量。然后，下一次r有4个元素，(conj stack ...将不会追加r，但它的前缀，因为这是conj应用于列表时的行为。从docs引用：

;;注意与矢量结合在一起完成

;;注意与列表结合是在开始时完成的

这当然破坏了预期的算法，并解释了你得到的错误结果。

类似的问题发生在(reverse r)哪returns a seq，即使r是一个载体。

例如，您可以通过应用(into [] ...)来解决该问题，您希望将列表作为向量传递。我看你需要做的两个景点：没有需要未决

(defn read-quad-tree [pattern] 
    (loop [r     [] 
     [s & rs :as stack] [] 
     [p & rp :as pending] (reverse pattern)] 
    (cond (nil? pending) (first r) 
      (= (count r) 4) (recur [] (conj stack (into [] (reverse r))) pending) 
      (= p \p)  (recur (conj r s) (into [] rs) rp) 
      :else   (recur (conj r p) stack rp)))) 

的修复，因为它从来没有“感染”与列表类型的其他名称。

当校正代码被称为是这样的：

(println (read-quad-tree "ppwwppwwppwwpbbbbwwwwbbwwbwbw")) 

它将输出：

[[[b b b b] w w [w w w w]] w w [[b b w w] w w [b w b w]]] 

虽然查找问题，我还添加了一些检查上（上）有效模式，其可能会感兴趣。扩展的代码如下：

(defn read-quad-tree [pattern] 
    (loop [r     [] 
      [s & rs :as stack] [] 
      [p & rp :as pending] (reverse pattern)] 
     (cond 
      (nil? pending) 
       (if (or (seq stack) (not= (count r) 1)) 
        {:error "Too few 'p'"} 
        {:tree (first r)}) 
      (= (count r) 4) 
       (recur [] (conj stack (into [] (reverse r))) pending) 
      (= p \p) 
       (if (empty? s) 
        {:error (format "'p' at %s lacks %d children" (count pending) (- 4 (count r)))} 
        (recur (conj r s) (into [] rs) rp)) 
      :else 
       (recur (conj r p) stack rp)))) 

它会返回一个地图，包含树关键，如果一切顺利的话，或与错误关键，如果该模式是不完整的。