有一个很棒的问题集叫做九十九Prolog Problems .问题 P70 就是标题中提到的问题。这是一个很棒的 Prolog solution这个问题只需要 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).
最佳答案
问题定义
(取自P-99: Ninety-Nine Prolog Problems)
我们假设多路树的节点包含单个字符。在其节点的深度优先顺序序列中,每当在树遍历过程中回溯到上一层时,都会插入一个特殊字符^
。
通过这个规则,图中的树表示为:afg^^c^bd^e^^^
(来源:ti.bfh.ch)
定义字符串的语法,在给定String
时,编写谓词tree(String,Tree)
构造Tree
。使用原子(而不是字符串)。使您的谓词双向工作。
解决方案第 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
节点的使用简化了事情。本质上算法如下:
- 从左到右扫描字符串
- 每当遇到节点标签时,我们都会创建一个新节点
- 该节点被栈顶采用
- 然后该节点被插入堆栈并成为新的顶部
- 当我们遇到
'^'
时,我们简单地从栈顶弹出
解决方案第 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('^')
如问题中所述,每当回溯到上一层时,我们都会插入 ^
。
关于algorithm - 从节点串构造多路树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3351679/