在 lisp 中转换树 [英] transforming trees in lisp

问题描述

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

(defun 变换(l)(条件((null l) NIL)((和(不是(numberp(car l)))(=(cadr l)0)(null(cddr l)))(缺点(汽车升)'(NIL NIL)))((和(不是(numberp(car l)))(=(cadr l)0))(cons (cons (car l) '(NIL NIL) ) (list (transform (cddr l)))))((不是(numberp (car l)))(cons (car l) (list (transform (cddr l)))))( T (变换 (cdr l)))))(defun subarbst(l nr)(条件( (= nr 0) nil)((原子升)升)( (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)(条件( (= nr 1) (subarbst l nr))((原子升)升)( T (subarbdr (cddr l) (+ (car (cdr l)) (- nr 1))))))(defun transf(l)(条件( (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"价值观?..提前谢谢你！

解决方案

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

main 函数的结构非常简单:

(defun 变换(l)(如果(空 l)零(树序列 l)))

而辅助函数基于以下思想:在每次调用时，将要转换的列表的其余部分传递给函数，该函数返回一对值:

1. 经过函数变换的树，

2. 列表的其余部分跟随列表中用于构建第一个值的部分.

这样，在每个递归步骤中，函数本身都可以使用第二个值来继续变换树.

这是函数:

(defun 树序列(l)(案例(干部 l)(0 (values (list (car l)) (cddr l)))(1 (multiple-value-bind (left-subtree rest-of-list)) (树序列 (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 仅使用返回的第一个值，即树.>

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

I'm trying to modify a representation of a tree from : (A 2 B 0 C 2 D 0 E 0) in (A (B) (C (D) (E))). My code is like:

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

but, instead of the second form, I get sth like: (A (B NIL NIL) (C (D NIL NIL) (E NIL NIL))), can anyone tell me why I do get those "NIL" values? .. Thank you in advance!

解决方案

Here is a possible solution, in which an auxiliary function tree-sequence is used. Note that the functions do not check for the validity of the input list.

The main function has a very simple structure:

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

while the auxiliary function is based on the following idea: at each call, the rest of the list to be transformed is passed to the function, that returns a pair of values:

1. The tree that has been transformed by the function,

2. The rest of the list following the part of the list used to build the first value.

In this way, at each recursive step, the function itself can use the second value to continue to transform the tree.

Here is the function:

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

Note the the couple of values returned are used only in the function tree-sequence, while transform uses only the first value returned, which is the tree.

Finally, note that this approach works for any kind of elements as nodes of the tree, including integers.

这篇关于在 lisp 中转换树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！