Multiline tree from node string

Question

There is a wonderful set of problems called Ninety-Nine Protocol Problems . The P70 challenge is what the title says. And here is a great Prolog solution to this problem, which takes only 5 lines. However, my understanding of Prolog is limited.

How does this solution look in C form (no itertools available)?

Edited on request. I hope I do not violate copyrights.

Problem:

The syntax in BNF is:

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

Good solution using difference lists:

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

Problem definition

_{(taken from P-99: Ninety-nine Prolog issues )}

, . ^ , .

: afg^^c^bd^e^^^

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 node . , :

• , node, node
  • , node
  • node
• '^',

---

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

, ^ , .