converting string list to ternary tree in sml

Question

I would like to convert a string list into ternary tree.The tree should have the following datatype

datatype ttree = node of string*ttree list*string|leaf of string*string*string

for example,

["<root>","<a3>","<b2>","Father","</b2>","<b3>","Mother","</b3>","</a3>","<a1>","<ffx>","AAA",...] : string list

should be converted to

val test = 
node
("<root>",
 [node
    ("<a3>",
     [leaf ("<b2>","Father","<b2>"),leaf ("<b3>","Mother","<b3>")],
     "<a3>"),
  node
    ("<a1>",[leaf ("<ffx>","AAA","<ffx>"),leaf ("<ff>","BBB","<ff>")],
     "<a1>")],"<root>") : ttree

Answer 1

Not the most efficient solution, but this should solve the problem:

datatype ttree = node of string*ttree list*string | leaf of string*string*string

val l = ["<root>",
          "<a3>",
            "<b2>","Father","</b2>",
            "<b3>","Mother","</b3>",
          "</a3>",
          "<a1>",
            "<ffx>","AAA","</ffx>",
          "</a1>"]

(*listToTree(l) = string list to ternary tree*)
fun listToTree(l : string list) : ttree =
  let
    (*isLeaf(s1, s3) = true if s1=<a> and s3=</a>, 
                        a can be replaced with anything
                       false otherwise*)
    fun isLeaf(s1 : string, s3 : string) : bool =
      let
        val (e1, e3) = (explode s1, explode s3)
        val (t1c1::t1) = e1
        val t1e = List.last t1
        val (t3c1::t3c2::t3) = e3
        val t3e = List.last t3
      in
        if t1c1 = #"<" andalso 
           t1c1 = t3c1 andalso 
           t1e = #">"  andalso
           t1e = t3e   andalso
           t3c2 = #"/" andalso
           t1 = t3     then true else false
      end

    (*parseUntil(l, until, acc) = (p, r),
      where p = acc + a part of l until an element x 
                that satisfies isLeaf(until,x)
        and r = elements of list l after x *)
    fun parseUntil(l : string list, until : string, acc : string list)
           : string list * string list =
      case l of
          []    => (rev acc, [])
        | x::xs => if isLeaf(until, x) 
                   then (rev acc, xs) 
                   else parseUntil(xs, until, x::acc)

    (*parseList(l) = the ttree list of the given string list*)
    fun parseList(l : string list) : ttree list =
      case l of
          [] => []
        | x::xs => let
          val (parsed, rest) = parseUntil(xs, x, [])
        in
          if length parsed = 1 
          then leaf(x, hd xs, x)::parseList(rest)
          else node(x, parseList(parsed), x)::parseList(rest)
        end
  in
    hd (parseList l)
  end

val result = listToTree l;

It is basically doing this:

• Once you get a tag, get the list elements until the close tag.

• Call the same parser function with the elements until the close tag and put the result in the list in the node.

• Call the same parser function with the elements after the close tag, and append them to the upper level list.

I hope I could help.