2

我正在尝试使用 GNU ClISP 在 Common Lisp 中编写一个程序来编译它。我想输入一个列表，例如(A(B (C) ()) (D (E) (F (G) ())))并根据第一个单词打印出前序、中序或后序遍历。例子：

(pre '(A(B (C)... etc))

我无法将我的逻辑放入 Clisp 表示法中。我目前有以下代码：

(defun leftchild (L)(cadr L))

(defun rightchild (L)(caddr L))

(defun data (L)(car L))

(defun pre (L)(if (null L) '()((data L)(pre(leftchild L))(pre(rightchild L)))))

... similar in and post functions

我收到编译错误，说我应该在我的 pre 函数中使用 lambda。我认为这是由于双 (( 在 data 前面，因为它需要一个命令，但我不确定应该放什么。我不认为 cond 会起作用，因为这会阻碍递归循环。另外，数据 L 会按现在的样子打印吗？编译器无法识别(print (data L)).

我已经在这个代码上工作了一个多星期，试图自己解决它，但我不知所措。如果有人能解释我做错了什么，我将不胜感激。

我的另一个问题是如何让程序提示用户输入 (pre '(A... etc)) 以便当我运行编译文件时程序将运行而不是给出 funcall 错误?

感谢您的时间。

4

1 回答 1

1

简短回答：如果您想使用if，请注意，您需要 aprogn以便在后续和替代情况下拥有多个表格。

长答案 - 还解释了如何遍历在列表中累积访问节点：

我想这是家庭作业，所以我不会给你一个完整的解决方案，但你的问题表明你的想法基本上是正确的，所以我将向你展示一个简单、惯用的方法来做到这一点。

首先，你是对的：未引用形式的car应该是一个函数(foo ...)，所以基本上像foo一个错误。请注意，这不适用于特殊形式和宏（例如cond，例如）。这些可以改变评估规则，并不是所有看起来(foo bar)都必须是由正常评估规则评估的形式。最简单的例子是，它只是返回未quote计算的参数，因此(quote (foo bar))不会出错。

现在，关于你的问题：

一个简单的解决方案是有一个累加器和一个遍历树的递归辅助函数，并将值推送到累加器中。像这样的东西：

(defun pre (node)
  (let ((result (list)))
    (labels ((rec (node)
               (cond (...
                      ...
                      ...))))
      (rec node)
      (nreverse result))))

刚刚引入了labels一个本地辅助函数，它将执行实际的递归，而外部let为您提供了一个累加器来收集节点值。此解决方案将结果作为列表返回。如果您只想打印每个节点的值，则不需要累加器或辅助函数。只需打印而不是推送，并使助手成为您的顶级功能。

请记住，您需要一个递归停止的基本情况。你应该在cond. 然后，您将需要每个子树的递归步骤，并且您需要将节点的值推送到结果中。您执行这些步骤的顺序决定了您是进行前序、中序还是后序遍历。你的代码表明你已经理解了这个原理，所以你只需要让它在 Lisp 代码中工作。您可以使用push将值推送到result，并consp检查节点是否为非空列表。由于空列表没有什么可做的，因此您基本上只需要在 中进行一项测试，但您也可以像在代码中那样cond显式检查节点是否为 。null

于 2011-10-10T08:55:00.610 回答