Многоходовое построение дерева из строки узла - PullRequest
Новая
       35

Многоходовое построение дерева из строки узла

5 голосов
/ 28 июля 2010

Существует замечательный набор задач, который называется «Девяносто девять» Prolog Задачи .Проблема P70 упоминается в заголовке.И вот отличное решение этой проблемы Prolog , которое занимает всего 5 строк.Однако мое понимание Пролога ограничено.

Как это решение выглядит в C-образной форме (нет доступных itertools)?

Отредактировано по запросу.Я надеюсь, что я не нарушаю авторские права.

Проблема:

Синтаксис в BNF: 

tree ::= letter forest '^'
forest ::= | tree forest

Хорошее решение с использованием списков различий: 

tree(TS,T) :- atom(TS), !, atom_chars(TS,TL), tree_d(TL-[ ],T). % (+,?)
tree(TS,T) :- nonvar(T), tree_d(TL-[ ],T), atom_chars(TS,TL).   % (?,+)
tree_d([X|F1]-T, t(X,F)) :- forest_d(F1-['^'|T],F).
forest_d(F-F,[ ]).
forest_d(F1-F3,[T|F]) :- tree_d(F1-F2,T), forest_d(F2-F3,F).

1 Ответ

3 голосов
/ 28 июля 2010

Определение проблемы

(взято из P-99: Девяносто девять проблем с прологом )

Мы предполагаем, что узлы многолучевого дерева содержат отдельные символы. В последовательности его узлов по глубине первого порядка был добавлен специальный символ ^ всякий раз, когда во время обхода дерева перемещение возвращается на предыдущий уровень.

По этому правилу дерево на рисунке представлено как: afg^^c^bd^e^^^

alt text

Определите синтаксис строки и напишите предикат tree(String,Tree), чтобы создать Tree, когда задано String. Работа с атомами (вместо строк). Заставьте ваш предикат работать в обоих направлениях.

Решение Часть 1: String2Tree

Это легко с помощью стека. Вот псевдокод: 

FUNCTION String2Tree(String str) : Tree
   LET st BE New-Stack<Node>
   LET root BE New-Node
   st.push(root)

   FOREACH el IN str
      IF el IS '^'
         st.pop()
      ELSE
         LET child BE New-Node(el)
         LET top BE st.top()
         top.adopt(child)
         st.push(child)

   RETURN New-Tree(root)

Использование фиктивного root узла упрощает дело. По сути, алгоритм выглядит следующим образом:

  • Сканирование строки слева направо
  • Всякий раз, когда мы сталкиваемся с меткой узла, мы создаем новый узел
    • Этот узел принимается вершиной стека
    • Затем этот узел помещается в стек и становится новым верхом
  • Когда мы сталкиваемся с '^', мы просто выскакиваем с вершины стека

Решение Часть 2: Tree2String

Противоположное направление - это вопрос простой рекурсии: 

FUNCTION string(Tree t) : String
   LET sb BE New-StringBuffer

   visit(t.root, sb)

   RETURN New-String(sb)

PROCEDURE visit(Node n, StringBuffer sb)
   sb.append(n.label)

   FOREACH child IN n.children()
      visit(child, sb)

   sb.append('^')

Как указано в задаче, мы вставляем ^ всякий раз, когда возвращаемся к предыдущему уровню.

...