Common Lisp Binary Tree

Question

Я пытаюсь написать программу на Common Lisp, используя GNU ClISP для ее компиляции. Я хотел бы ввести список, например (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

Я получаю ошибки компиляции, говорящие, что я должен использовать лямбду в своей предварительной функции. Я думаю, что это связано с двойной ((infront данных, потому что он ожидает команду, но я не уверен, что я должен поместить туда. Я не думаю, что cond будет работать, потому что это помешает рекурсивный цикл. будут ли данные L печататься как есть? Компилятор не распознал (print (data L)).

Я работаю над этим кодом уже более недели, пытаясь устранить его самостоятельно, но я в растерянности. Я был бы очень признателен, если бы кто-то мог объяснить, что я делаю неправильно.

Другой вопрос, который у меня возникает, состоит в том, как заставить программу предложить пользователю ввести строку (pre '(A ... и т. Д.)), Чтобы при запуске скомпилированного файла программа запускалась вместо ошибка funcall?

Спасибо за ваше время.

Answer 1

Краткий ответ: Если вы хотите использовать if, обратите внимание, что вам понадобится progn, чтобы иметь более одной формы в последующих и альтернативных случаях.

---

Longответ - также объясняет, как пройти через накопление посещенных узлов в списке:

Я предполагаю, что это домашняя работа, поэтому я не дам вам полного решения, но ваш вопрос показывает, что у вас в основном правильная идея,так что я покажу вам простой идиоматический способ сделать это.

Во-первых, вы правы: машина без кавычек должна быть функцией, поэтому, в принципе, все что угодно, как (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.Затем вам понадобятся рекурсивные шаги для каждого поддерева, и вам нужно будет подтолкнуть значение узла к результатам.Порядок, в котором вы выполняете эти шаги, определяет, будете ли вы выполнять обход до, во время или после заказа.Ваш код показывает, что вы уже понимаете этот принцип, поэтому вам просто нужно заставить его работать в Лисп-коде.Вы можете использовать push, чтобы переместить значения в result, и consp, чтобы проверить, является ли узел непустым списком.Поскольку для пустых списков ничего не нужно делать, вам, в основном, понадобится только один тест в cond, но вы также можете явно проверить, является ли узел null, как вы делали в своем коде.