5

私は次のClojureとして実装したポストオーダーの深さ優先トラバーサルを使用してトラバースする必要があるANTLR3 ASTを持っています:

(defn walk-tree [^CommonTree node]
  (if (zero? (.getChildCount node))
    (read-string (.getText node))
    (execute-node
      (map-action node)
      (map walk-tree (.getChildren node)))))))

これを loop...recur を使用して末尾再帰に変換したいのですが、ポストオーダー トラバーサルが必要なため、これを行うために明示的なスタックを効果的に使用する方法を理解できませんでした。

4

3 に答える 3

8

ツリーをトラバースして各ノードを訪問する末尾再帰ソリューションを生成する代わりに、関数を使用して深さ優先トラバーサルの遅延シーケンスをtree-seq生成し、トラバーサル内の各オブジェクトからテキストを取得できます。レイジー シーケンスは、シーケンス内の次のアイテムを生成するために必要なすべての状態をヒープに格納するため、スタックを破壊することはありません。これらは、このような再帰的なソリューションの代わりに非常に頻繁に使用され、loopよりrecur困難な場合に使用されます。

典型的な答えは次のようになりますが、あなたの木がどのように見えるかはわかりません。「子供がいる」「子供のリスト」関数で遊ぶ必要があります

(map #(.getText %) ;; Has Children?      List of Children    Input Tree
     (tree-seq #(> (.getChildCount #) 0) #(.getChildren %) my-antlr-ast))

tree-seq がニーズに合わない場合は、ツリーから遅延シーケンスを生成する他の方法があります。次にzipperライブラリを見てください。

于 2012-09-11T23:07:06.557 に答える
5

おっしゃるように、末尾再帰を使用してこれを実装する唯一の方法は、明示的なスタックの使用に切り替えることです。考えられるアプローチの1つは、ツリー構造を、本質的にツリーの逆ポーランド記法表現であるスタック構造に変換することです（これを実現するためにループと中間スタックを使用します）。次に、別のループを使用してスタックをトラバースし、結果を構築します。

これを実現するために私が作成したサンプルプログラムを次に示します。末尾再帰をインスピレーションとして使用して、ポストオーダーでJavaコードを使用します。

(def op-map {'+ +, '- -, '* *, '/ /})

;; Convert the tree to a linear, postfix notation stack
(defn build-traversal [tree]
  (loop [stack [tree] traversal []]
    (if (empty? stack)
      traversal
      (let [e (peek stack)
            s (pop stack)]
        (if (seq? e)
          (recur (into s (rest e)) 
                 (conj traversal {:op (first e) :count (count (rest e))}))
          (recur s (conj traversal {:arg e})))))))

;; Pop the last n items off the stack, returning a vector with the remaining
;; stack and a list of the last n items in the order they were added to
;; the stack
(defn pop-n [stack n]
  (loop [i n s stack t '()]
    (if (= i 0)
      [s t]
      (recur (dec i) (pop s) (conj t (peek s))))))

;; Evaluate the operations in a depth-first manner, using a temporary stack
;; to hold intermediate results.
(defn eval-traversal [traversal]
  (loop [op-stack traversal arg-stack []]
    (if (empty? op-stack)
      (peek arg-stack)
      (let [o (peek op-stack)
            s (pop op-stack)]
        (if-let [a (:arg o)]
          (recur s (conj arg-stack a))
          (let [[args op-args] (pop-n arg-stack (:count o))]
            (recur s (conj args (apply (op-map (:op o)) op-args)))))))))

(defn eval-tree [tree] (-> tree build-traversal eval-traversal))

あなたはそれをそのように呼ぶことができます：

user> (def t '(* (+ 1 2) (- 4 1 2) (/ 6 3)))
#'user/t
user> (eval-tree t)
6

これをAntlrAST構造で動作するように変換するための演習として読者に任せます;）

于 2012-09-11T18:10:51.457 に答える
1

私はclojureに熟練していませんが、あなたが探しているものは理解していると思います。

これがいくつかの擬似コードです。ここでの擬似コードのスタックはステートフルオブジェクトのように見えますが、代わりに不変のものを使用することは非常に現実的です。O（ツリーの深さ*ノードあたりの最大子）ヒープのようなものを使用します。

walk_tree(TreeNode node) {
    stack = new Stack<Pair<TreeNode, Boolean>>();
    push(Pair(node, True), stack)
    walk_tree_aux(stack);
}
walk_tree_aux(Stack<Pair<TreeNode, Boolean>> stack) { -- this should be tail-recursive
    if stack is empty, return;
    let (topnode, topflag) = pop(stack);
    if (topflag is true) {
        push Pair(topnode, False) onto stack);
        for each child of topnode, in reverse order:
            push(Pair(child, True)) onto stack
        walk_tree_aux(stack);
    } else { -- topflag is false
        process(topnode)
        walk_tree_aux(stack);
    }
}
于 2012-09-12T15:42:07.950 に答える