如何走路尾递归的AST Clojure中

我有一个ANTLR3 AST，我需要用我曾作为大致实施以下Clojure的一个订单后，深度优先遍历遍历：如何走路尾递归的AST Clojure中

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

我想使用循环... recur将其转换为尾递归，但由于我需要一个后序遍历，所以我一直无法弄清楚如何有效地使用显式堆栈来实现这一点。

来源

2012-09-11 Kyle Goodwin

而是产生的遍历树并访问每个节点尾递归的解决方案，可以产生深度优先遍历的懒顺序使用tree-seq函数，然后获取文本列于遍历每个对象的。 懒惰序列从不吹动堆栈，因为它们存储生成堆中序列中下一项所需的所有状态。它们经常被用来代替这种递归解决方案，其中loop和recur更难以分辨。

我不知道你的树看起来像什么，虽然典型的答案看起来像这样。您需要与孩子的“有孩子”“列表进行播放”功能

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

如果树-SEQ不能满足您的需求，还有其他的方式来产生从树懒序列。接下来看看拉链库。

来源

2012-09-11 23:07:06

尽管我希望我能接受这个答案和下面使用堆栈的答案，但这确实是更好的解决方案，即使它不是我所想的。感谢您让我更好地思考这个问题！ –

FWIW，tree-seq给出了预购遍历，而不是后序。老实说，我认为这里最简单的解决方案是'clojure.walk/postwalk'，如果可能的话我会使用它。如果真的存在堆栈的危险，那么拉链就可以工作，尽管对它们进行真正的后序遍历可能会非常棘手。无论他们是否适合这个特殊问题，拉链都是你的军火库中的绝佳工具:) – Alex

至于你提到，要实现这个用尾递归的唯一方法是切换到使用一个明确的堆栈。一种可能的方法是将树结构转换为基本上是树的逆波兰表示法的堆栈结构（使用循环和中间堆栈来完成此操作）。然后，您将使用另一个循环来遍历堆栈并建立结果。

下面是我写的做到这一点，使用Java代码在postorder using tail recursion作为灵感的示例程序。

(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

我把它作为一个练习，读者将它转换为一个ANTLR的AST结构工作;）

来源

2012-09-11 18:10:51 Alex

我不擅长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-12 15:42:07 NovaDenizen

如何走路尾递归的AST Clojure中

回答

相关问题