views:

61

answers:

1

There is a wonderful problem set called Ninety-Nine Prolog Problems. Problem P70 is the one referred to in the title. And here is a great Prolog solution of this problem which takes only 5 lines. However, my understanding of Prolog is limited.

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

Edited by request. I hope I do not violate copyright.

The problem:

Syntax in BNF:

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

A nice 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).
+3  A: 

Problem Definition

(taken from P-99: Ninety-Nine Prolog Problems)

We suppose that the nodes of a multiway tree contain single characters. In the depth-first order sequence of its nodes, a special character ^ has been inserted whenever, during the tree traversal, the move is a backtrack to the previous level.

By this rule, the tree in the figure is represented as: afg^^c^bd^e^^^

alt text

Define the syntax of the string and write a predicate tree(String,Tree) to construct the Tree when the String is given. Work with atoms (instead of strings). Make your predicate work in both directions.


Solution Part 1: String2Tree

This is easy with a stack. Here's the 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)

The use of a dummy root node simplifies matters. Essentially the algorithm is as follows:

  • Scan the string left to right
  • Whenever we encounter a node label, we create a new node
    • That node is adopted by the top of the stack
    • That node is then pushed to the the stack and becomes the new top
  • When we encounter a '^', we simply pop off the top of the stack

Solution Part 2: Tree2String

The opposite direction is a matter of simple recursion:

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

As specified in the problem, we insert ^ whenever we backtrack to the previous level.

polygenelubricants
This is a very nice solution. Thank you polygenelubricants! Typo: 'Tree2String' missing. What happens in 'visit' if the child has no children?
John
@John: yes, `FUNCTION string` should be `FUNCTION Tree2String`. When there are no children then `FOREACH` will be a no-op loop, which is exactly what we want. I'll add this correction/clarification with next revision, along with other things I might add.
polygenelubricants