Tree construction from a node string

题目

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 opposite is represented as: afg^^c^bd^e^^^

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.

解题思路

先用BNF定义字符串语法：

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

这个题目包含两部份：

1. 将多路树转换成字符中
2. 将字符中转换成多路树

将多路树转换成字符串

用单元测试描述为：

多路树是一个递归结构，所以我们自然而然地想到用递归方法解决。

假设当给定的多路树只有一个节点，比如(a,[])，如何构造字符串呢？

先输出根节点，再发现子树列为空即已到达子树列表末尾，则输出^。

假设给定的多路树再复雑一点，拥有两层结构，根节点拥有两棵树子树，比如(a,[(b,[]),(c,[])])，如何构造字符串呢？

先轮出根节点，再将子树逐一转换为字符串，最后再输出^。

归纳起来，将多路树转换为字符串的方法为：

1. 先输出根节点
2. 再将子树逐转换为字符串，因为每棵子树都是三多路树，所以这𥚃套用步骤1至3到每一棵子树上
3. 输出'^'

举一个复雑一点的例子，给定如下三路树：

• 先输出根节点a，再逐一转换三棵子树
  • 转换子树(f,[(g,[])])
    • 先输出节点f，再逐一转换唯一的子树
      • 转换子树(g,[])
        • 先轮出节点值g
        • 子树列为空，即到达子树列表末尾，输出'^'
    • 到达子树列表末尾，输出'^'
  • 转换第二棵子树`(c,[])
    • 先输出节点值c
    • 子树列表为空，即到达子树列表末尾，输出'^'
  • 转换第三棵子树(b,[(d,[]),(e,[])])
    • 先输出节点值b，再逐一转换子树
      • 转换子树(d,[])
        • 先输出节点值d
        • 子树列表为空，即到达子树列表末尾，输出'^'
      • 转换子树(e,[])
        • 先输出节点值e
        • 子树列表为空　即到达子树列表末尾，输出'^'
    • 到达子树列表末尾，输出'^'
• 到达子树列表末尾，输出'^'

代码实现：

reduce是Python标准库提供的一个函数式的工具，其声明为：

reduce(function, iterable, initializer)

其功能是将function累积地、从左往右作用于iterable中的每一个元素。

reduce相当于如下代码：

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

这𥚃我们使用reduce将列表中的所有字符串拼接起来。

将字符串转换为多路树

用单元测试描述为：

一样用递归方法解决。一个字符串是由一个节点字符（第一个字符）、表示零至多个子树的字符串和'^'组。将字符串转换为多路树的方法：

1. 先取出第一字符作为节点值
2. 从剩余子符串中解析出零至多个子树。所有子树都是多路树，所以这𥚃套用步骤1至3解析每一棵子树
3. 直至遇到字符'^'，一棵完整的多路树解析完毕

举个例子，给定字符串afg^^c^bd^e^^^。

• 取出第一个字符a做为节点值，剩余fg^^c^bd^e^^^
• 从剩余字符串fg^^c^bd^e^^^中解柝出零至多个多路树
  • 解柝第一棵子树
    • 取出第一个字符f做为节点值，剩余字符串g^^c^bd^e^^^
    • 从剩余字符串中解柝出零至多个多路树
      • 解柝第一棵子树
        • 取出第一个字符g做为节点值
        • 从剩余字符串^^c^bd^e^^^中取出第一个符为^，已解柝出一棵多路树(g,[])
    • 从剩余字符串^c^bd^e^^^中取出第一个字符为^，表明已解柝出一棵多路树(f,[(g,[])])
  • 解柝第二棵子树
    • 从剩余字符中c^bd^e^^^中取出第一个字符c做为节点值，剩余^bd^e^^^
    • 从剩余字符串^bd^e^^^中取出第一个字符为^，表明已解柝出一棵多路树(c,[])
  • 解柝第三棵子树
    • 从剩余字符串bd^e^^^中取出第一个字符b做为节点值，剩余d^e^^^
    • 从剩余字符串中解柝出零至多个多路树
      • 解析第一棵子树
        • 从剩余字符串d^e^^^中取出第一个字符d做为节点值
        • 从剩余字符串中取出第一个字稔为^，表明已解柝出一棵多路树(d,[])
      • 解柝第二棵子树
        • 从剩余字符串e^^^中取出第一个字符e做为节点值
        • 从剩余字符串^^^中取出第一个字符^，表明已解柝出一棵多路树(e,[])
    • 从剩余字符串^^中取出第一个字符^，表明已解柝出一棵多路树(b,[(d,[]),(e,[])])
• 从剩余字符串^中取出第一个字符为^，表明已解柝出一棵多路树(a,[(f,[(g,[])]),(c,[]),(b,[(d,[]),(e,[])])])

代码实现：

字符串多路树多向转换

代码实现：

使用Python内建函数type(v)检测输入值类型。当输入值类型为元组「tuple」即多路树时，调用tree_to_string(t)。否则，调用string_to_tree(s)。