在 lisp 中转换树

Question

我正在尝试修改树的表示形式：(A 2 B 0 C 2 D 0 E 0) in (A (B) (C (D) (E)))。我的代码是这样的：

(defun transform(l)
 (cond
   ( (null l) NIL)
   ( (and (not (numberp (car l))) (= (cadr l) 0) (null (cddr l)))
        (cons (car l) '(NIL NIL) ))  
   ( (and (not (numberp (car l))) (= (cadr l) 0))
       (cons (cons (car l) '(NIL NIL) ) (list (transform (cddr l))))) 
   ( (not (numberp (car l))) 
         (cons (car l) (list (transform (cddr l)))))
   ( T (transform (cdr l)))
 ))

 (defun subarbst(l nr)
 (cond
    ( (= nr 0) nil)
    ( (atom l) l)
    ( ( numberp (car l)) (cons (car l) (subarbst (cdr l) nr)))
    ( (and (= nr 1) (= (cadr l) 0)) (list (car l) (cadr l))) 
    ( T (cons (car l) (subarbst (cdr l) (+ (car (cdr l)) (- nr 1)))))
)
) 

 (defun subarbdr(l nr)
 (cond 
   ( (= nr 1) (subarbst l nr))
   ( (atom l) l)
   ( T (subarbdr (cddr l) (+ (car (cdr l)) (- nr 1))))
 )
)

(defun transf(l)
(cond 
  ( (null l) nil)
  ( (= 0 (cadr l)) (cons (car l) '(nil nil)))
  ( (= 1 (cadr l)) (list (car l) (transf (subarbst (cddr l) '1))))
  ( (= 2 (cadr l)) (list (car l)
                       (transf (subarbst (cddr l) '1))
                       (transf (subarbdr (cddr l) '2))))
))

但是，我得到的不是第二种形式，而是像：(A (B NIL NIL) (C (D NIL NIL) (E NIL NIL)))，谁能告诉我为什么我得到那些 "NIL"值？ .. 提前致谢！

Answer 1

这是一个可能的解决方案，其中使用了辅助功能tree-sequence。请注意，这些函数不会检查输入列表的有效性。

main函数的结构非常简单：

(defun transform(l)
  (if (null l)
      nil
      (tree-sequence l)))

而辅助函数基于以下想法：在每次调用时，将要转换的列表的其余部分传递给函数，即 returns 一对值：

经过函数变换的树，
列表的其余部分在用于构建第一个值的列表部分之后。

这样，在每一步递归的时候，函数本身就可以使用第二个值继续变换树。

函数如下：

(defun tree-sequence(l)
  (case (cadr l)
    (0 (values (list (car l)) (cddr l)))
    (1 (multiple-value-bind (left-subtree rest-of-list) (tree-sequence (cddr l))
          (values (list (car l) left-subtree) rest-of-list)))
    (t (multiple-value-bind (left-subtree rest-of-list) (tree-sequence (cddr l))
          (multiple-value-bind (right-subtree rest-of-rest) (tree-sequence rest-of-list)
             (values (list (car l) left-subtree right-subtree) rest-of-rest))))))

请注意，返回的两个值仅在函数 tree-sequence 中使用，而 transform 仅使用返回的第一个值，即树。

最后，请注意，此方法适用于作为树节点的任何类型的元素，包括整数。

Answer 2

此问题的答案由给出，作为对显然正在解决相同家庭作业问题的用户的回应的一部分。解决方案是基于将前缀符号反转为后缀，然后将其解释为用于构建树的基于堆栈的反向抛光符号。

巧合的是，该答案中的以下代码产生了与您要求的相同的表示形式。我即兴想出了那个表示，为了解决那个问题中的中序遍历问题：

(defun build-tree (syntax)
  (let ((rs (reverse syntax))
        (stack))
    (dolist (item rs (pop stack))  ;; heart of the interpreter loop
      (cond ((integerp item) (push item stack))  ;; integer instruction
            ((symbolp item) (let ((num (pop stack)))  ;; sym instruction
                              ;; construct node using backquote, and
                              ;; put it on the stack.
                              (push `(,item ,@(loop repeat num
                                                    collect (pop stack)))
                                    stack)))))))

在 lisp 中转换树

transforming trees in lisp

lisp

tree

common-lisp