改变Lisp中的树木 [英] transforming trees in lisp

问题描述

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

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

但是，我得到的不是第二种形式，而是:(A(B NIL NIL)(C(D NIL NIL)(E NIL NIL))))，有人可以告诉我为什么我得到那些"NIL"价值观? .. 预先谢谢你！

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!

推荐答案

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

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. 已通过函数转换的树

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

列表的其余部分后面用于创建第一个值的列表部分.

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.

这是函数:

(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仅使用返回的第一个值，即树.

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屋！