3

数の木を定義する次の BNF を考えてみましょう。ツリーは、葉、1 つのサブツリーを持つノード 1、または 2 つのサブツリーを持つノード 2 のいずれかであることに注意してください。

tree ::= (’leaf number)
| (’node-1 tree)
| (’node-2 tree tree)

を。これらのツリーで再帰プロシージャのテンプレートを作成します。

b. t に含まれる葉の数を返す手続き (leaf-count t) を定義する

> (leaf-count ’(leaf 5))

1

> (leaf-count ’(node-2 (leaf 25) (leaf 17)))

2

> (leaf-count ’(node-1
(node-2 (leaf 4)
(node-2 (leaf 2) (leaf 3)))))

3

これが私がこれまでに持っているものです：

;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (car tree)))
(define (node? tree) (pair? (car tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

問題なく動作するはずですが、次のような単純なテストケースを使用して実行しようとすると

(leaf-count '(leaf 5))

次のエラー メッセージが表示されます。

car: 型ペアの引数が必要です。与えられた葉

このエラー メッセージはどういう意味ですか? リーフをリストとして定義しています。しかし、何らかの理由で、それが表示されず、エラーメッセージが表示されます。

4

3 に答える 3

5

他の人の課題を解決するのは確かに楽しいです。

(define leaf-count
  (match-lambda 
   [(list 'leaf x)     1]
   [(list 'node-1 t)   (leaf-count t)]
   [(list 'node-2 l r) (+ (leaf-count l) (leaf-count r))]))
于 2010-02-08T19:34:12.063 に答える
2

葉を引用し(leaf-count '(leaf 5))たので、それはシンボルであり、以前に定義した変数ではありません。それがエラーの原因ですが、修正する必要はありません。3 つの定義はあまり意味がなく、リーフまたはノードを検出する手順は BNF 仕様と一致しません。

これはあなた自身の例からのツリーです: ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))). node-1soで引用されてnode-2おりleaf、単なる記号であり、定義する必要はありません。上記のツリーのさまざまな要素が何であるかを検出できる関数を記述leaf?します。node?以下は、すべての関数呼び出しが true を返すテスト ケースです。

(define a-tree ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))))
(node? a-tree)
(node? (car (cdr a-tree)))
(leaf? (car (cdr (car (cdr a-tree)))))
(node? (car (cdr (cdr (car (cdr a-tree))))))
(leaf? (car (cdr (car (cdr (cdr (car (cdr a-tree))))))))

これが機能すると、カウントも問題になりません (現在の方法は機能しませんが、それを支援するために left-subtree および right-subtree 関数を作成することをお勧めします)。

于 2010-02-10T03:26:25.707 に答える
0

これが私がこれまでに持っているものです：

 ;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (cadr tree)))
(define (node? tree) (pair? (cadr tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

マイナーな調整で動作するようになりました。条件を変更して、情報が含まれているリストのcadrを確認します。この場合のリストの car は、データが何であるか (リーフ、ノードなど) の単なるラベルです。そうではありません。最も基本的なテストケースでは機能しましたが、次のようなより複雑なケースでは機能しませんでした

(leaf-count '(node-2 (leaf 25) (leaf 17)))
于 2010-02-10T00:06:23.987 に答える