표기법 스키마의 표기법

Question

다음 코드에 대해 "map-diff"함수가 올바르게 작동한다고 가정합니다. 산술 구문 분석 트리를 가져와 선주문 표기법으로 출력하는 방법에 대해 궁금합니다. 내 "사전 주문"기능 내에서 "지도 - 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은 list 대신 make-tree으로 정의해야합니다. 그리고 make-tree이 아닌 preorder의 죄수입니다. 지금 당신이 좋은 올바른 목록 형식이 아닌 출력으로 점으로 구분 된 목록을 얻는 방법입니다.

나는 당신의 노력을 준비하고, 그것을 파싱하기 위해 문자열에 캐스팅하는 것이 리스프 동적 타이핑을 고려해 볼 때 매우 이례적인 것인지 잘 모르겠습니다.

어쨌든 여기에 어떻게`지도 - diff`하지 '전순'에 2 번째의 인수가 하나의 가능성

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