P78 - Lisp-like tree representation (5)

There is a particular notation for multiway trees in Lisp.  Lisp is a prominent functional programming language.  In Lisp almost everything is a list.

Our example tree would be represented in Lisp as (a (f g) c (b d e)).  The following pictures give some more examples.

Note that in the “lispy” notation a node with successors (children) in the tree is always the first element in a list, followed by its children.  The “lispy” representation of a multiway tree is a sequence of atoms and parentheses ‘(’ and ‘)’, with the atoms separated by spaces.  We can represent this syntax as a Scala String.  Write a method lispyTree which constructs a “lispy string” from an MTree.

As a second, even more interesting, exercise try to write a method that takes a “lispy” string and turns it into a multiway tree.

[Note: Much of this problem is taken from the wording of the same problem in the Prolog set.  This is certainly one way of looking at Lisp notation, but it’s not how the language actually represents that syntax internally.  I can elaborate more on this, if requested.  <PMG>]