3

考虑以下定义数字树的 BNF。请注意，一棵树可以是叶子、具有一个子树的节点 1 或具有两个子树的节点 2。

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

一个。为这些树上的递归过程编写一个模板。

湾。定义返回 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))所以它是一个符号，而不是你之前定义的变量。那是错误的原因，但不是您应该解决的问题。您的三个定义没有多大意义，并且您检测叶子或节点的程序与 BNF 规范不匹配。

这是您自己的示例中的一棵树：’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))). 它是这样引用的，node-1只是符号，不需要定义。现在编写可以检测上述树的各种元素是什么的函数。这是一个测试用例，所有函数调用都应返回 true：node-2leafleaf?node?

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

一旦这个工作，计数也应该没有问题（尽管你当前的方法不起作用，我建议编写左子树和右子树函数来帮助你）。

于 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，因为它是包含信息的内容。在这种情况下，列表的汽车只是数据是什么（叶子、节点等）的标签。不完全的。我让它适用于最基本的测试用例，但不适用于更复杂的测试用例，例如

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