Mehrweg-Baumkonstruktion aus einer Knotenkette

Question

Es gibt ein wunderbares Problem-Set namens Ninety-Nine Prolog-Probleme . Das Problem P70 ist dasjenige, das im Titel genannt wird. Und hier ist ein großartiger Prolog Lösung dieses Problems, das nur 5 Zeilen umfasst. Mein Verständnis von Prolog ist jedoch begrenzt.

Wie sieht diese Lösung in einer C-ähnlichen Form aus (keine itertools verfügbar)?

Auf Wunsch editiert. Ich hoffe, ich verstoße nicht gegen das Urheberrecht.

Das Problem:

Syntax in BNF:

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

Eine schöne Lösung mit Differenzlisten:

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

Answer 1

Problemstellung

_{(entnommen aus <a href="https://web.archive.org/web/20160409014329/https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/" rel="nofollow noreferrer">P-99: Neunundneunzig Prolog-Probleme </a>)}

Wir nehmen an, dass die Knoten eines mehrseitigen Baums einzelne Zeichen enthalten. In der Reihenfolge der Knoten in der ersten Tiefe wird ein spezielles Zeichen ^ wurde immer dann eingefügt, wenn beim Durchlaufen des Baums ein Rücksprung zur vorherigen Ebene erfolgt.

Nach dieser Regel wird der Baum in der Abbildung wie folgt dargestellt: afg^^c^bd^e^^^

_{(Quelle: <a href="https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p70.gif" rel="nofollow noreferrer">ti.bfh.ch </a>)}

Definieren Sie die Syntax der Zeichenkette und schreiben Sie ein Prädikat tree(String,Tree) zur Konstruktion der Tree wenn die String gegeben ist. Arbeiten Sie mit Atomen (anstelle von Strings). Lassen Sie Ihr Prädikat in beide Richtungen funktionieren.

---

Lösung Teil 1: String2Tree

Mit einem Stapel ist das ganz einfach. Hier ist der Pseudocode:

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)

Die Verwendung einer Attrappe root Knoten vereinfacht die Sache. Der Algorithmus sieht im Wesentlichen wie folgt aus:

• Scannen der Zeichenfolge von links nach rechts
• Jedes Mal, wenn wir auf eine Knotenbeschriftung stoßen, erstellen wir einen neuen Knoten
  • Dieser Knoten wird von der Spitze des Stapels übernommen
  • Dieser Knoten wird dann auf den Stapel geschoben und wird der neue oberste
• Wenn wir auf eine '^' wird einfach der oberste Teil des Stapels abgehoben

---

Lösung Teil 2: Tree2String

Die umgekehrte Richtung ist eine Frage der einfachen Rekursion:

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

Wie in der Aufgabenstellung angegeben, fügen wir ein ^ wenn wir zur vorherigen Ebene zurückkehren.