transforming trees in lisp

问题:

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!

回答1:

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.

回答2:

An answer to this is given by https://stackoverflow.com/a/34193414/1250772 as part of a response to a user who is evidently working through the same homework problem. The solution is based on reversing the prefix notation into postfix, and then interpreting it as a stack-based reverse polish notation for constructing a tree.

By coincidence, the following code from that answer produces the same representation as what you're asking for. I came up with that representation impromptu, in order to solve the inorder traversal problem in that question:

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