tree - 在 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”值(value)观？ ..提前致谢!

Answer 1

https://stackoverflow.com/a/34193414/1250772 给出了这个问题的答案作为对显然正在解决相同家庭作业问题的用户的回应的一部分。该解决方案基于将前缀表示法反转为后缀，然后将其解释为用于构建树的基于堆栈的反向抛光表示法。

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

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