algorithm - 从节点字符串构造多路树

Question

有一个很棒的问题集叫做九十九Prolog Problems。问题 P70 是标题中提到的问题。这是这个问题的一个很好的 Prolog解决方案，只需要 5 行。但是，我对 Prolog 的理解是有限的。

这个解决方案在类似 C 的形式中看起来如何（没有可用的 itertools）？

应要求编辑。我希望我不侵犯版权。

问题：

BNF 中的语法：

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

使用差异列表的一个很好的解决方案：

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

问题定义

_{（取自P-99：九十九个序言问题）}

我们假设多路树的节点包含单个字符。在其节点的深度优先顺序序列中，^只要在树遍历期间，移动是回溯到上一层，就会插入一个特殊字符。

通过这个规则，图中的树表示为：afg^^c^bd^e^^^

_{（来源：ti.bfh.ch）}

定义字符串的语法并编写一个谓词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节点的使用简化了事情。本质上，算法如下：

• 从左到右扫描字符串
• 每当我们遇到节点标签时，我们都会创建一个新节点
  • 该节点被栈顶采用
  • 然后将该节点推入堆栈并成为新的顶部
• 当我们遇到 a 时'^'，我们只是简单地从栈顶弹出

---

解决方案第 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('^')

正如问题中所指定的，^每当我们回溯到上一个级别时，我们都会插入。