1

假设我的“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)
4

2 回答 2

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)))
于 2013-10-20T18:40:24.503 回答
0 
;; 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))
于 2013-10-20T20:57:25.300 回答