方案中的预序表示法

Question

假设我的"map-diff“函数对以下代码正常工作。我想知道如何获取一个算术解析树，并输出它的预置表示法。我希望能够在我的"preorder“函数中使用我的"map-diff”函数，但是我想不出如何继续这样做。我的基本病例正确吗？

(define (make-tree value left right) (list value left right)) 
(define (value tree) (car tree))
(define (left tree) (cadr tree))
(define (right tree) (caddr tree))

(define (prepare x)
  (cond ((number? x) (number->string x))
        ((char? x) (string x))))

(define x
  (map-diff (lambda (x) (prepare x)) 
    (list #\+ 
      (list #\*
         (list 3 '() '())
         (list 9 '() '()))
      (list #\+
         (list #\/ (list 5 '() '()) '())
         (list 4 '() '())))))


(define (preorder T)
  (cond ((null? T) "")
       ((eq? (value T) "+")
         (cons (value T) (cons (preorder (left T)) (preorder (right T)))))
       ((eq? (value T) "*")
        (cons (value T) (cons (preorder (left T)) (preorder (right T)))))
       ((eq? (value T) "-")
         (cons "-" (preorder (left T))))
       ((eq? (value T) "/")
         (cons "/" (preorder (left T))))
       (else (value T))))

(preorder x)

Answer 1

首先，不要把你的ADT和初级类型混为一谈。如果你定义了一个ADT，坚持它，考虑一下程序。X应该用make-tree而不是list来定义)。make-tree而不是preorder中的缺点。按照你现在的方式，你会得到一个虚线列表作为输出，而不是一个很好的合适的列表形式。

考虑到lisps动态类型，我不知道您试图用什么来准备，将一些东西转换成字符串来解析它们是相当不寻常的。

不管怎样，这里有一种可能性

(define (preorder T)
 (let ((top (prepare (value T))))
  (cond ((null? T) "")
        ((eq? top "+")
         (cons top (cons (preorder (left T)) (preorder (right T)))))
        ((eq? top "*")
         (cons top (cons (preorder (left T)) (preorder (right T)))))
        ((eq? top "-")
         (cons "-" (preorder (left T))))
        ((eq? top "/")
         (cons "/" (preorder (left T))))
        (else top)))

Answer 2

;; helper
(define (list-ref-at n)
  (lambda (l) (list-ref l n)))

;; node data type
(define (make-node value left right)
 `(NODE ,value ,left ,right))
(define node-value (list-ref-at 1))
(define node-left  (list-ref-at 2))
(define node-right (list-ref-at 3))

;; leaf data type (as special node)
(define (make-leaf value)
  (make-node value '() '()))
(define (node-is-leaf? node)
  (and (null? (node-left  node))
       (null? (node-right node))))

;; convert to list
(define (node->preorder-list node)
  (if (node-is-leaf? node)
      (node-value node)
      (let ((v (node-value node))
            (l (node-left  node))
            (r (node-right node)))
        (assert (not (null? l)))
        (if (null? r)
            (list v (node->preorder-list l)) ; unop
            (list v (node->preorder-list l) (node->preorder-list r)))))) ;binop

;; test
> (define x (make-node '* (make-node '+ (make-leaf 1) (make-leaf 2)) (make-leaf 10))
> (node->preorder-list x)
(* (+ 1 2) 10)
> (set! x (make-node '- x '()))
> (node->preorder-list x)
(- (* (+ 1 2) 10))