好吧，这是一个有点复杂的问题，但是 tl;dr 基本上是如何使用“模式树”解析“实际树”？如何检查特定树是否存在实例与特定模式树匹配？
首先，我们有模式树的结构。模式树一般可以包含以下类型的节点:
sequence节点:匹配项目序列(零个或多个)。可选节点:匹配一个或零个项目。class节点:委托(delegate)到另一个模式树进行匹配。first节点:匹配它从集合中找到的第一个子模式。interlace节点:以任意顺序匹配任何子模式。text节点:匹配直接文本。
这对于这个问题来说应该足够了。还有一些节点类型，但这些是主要的。本质上它就像正则表达式或语法树。
我们可以从一个简单的模式树开始:
<sequence>
<text value="foo">
<text value="bar" />
</text>
</sequence>
这应该与以下任何文本树匹配。
<foo><bar/></foo><foo><bar/></foo><foo><bar/></foo>
<foo><bar/></foo>
<foo><bar/></foo><foo><bar/></foo>
更具体地说，您应该将其想象为 JSON，并将模式树想象为 JSON。
{
"tag": "foo",
"children": [
{ "tag": "bar" }
]
}
序列模式树是这样的:
{
"type": "sequence",
"children": [
{
"type": "text",
"value": "foo",
"children": [
{
"type": "text",
"value": "bar"
}
]
}
]
}
对于模式树来说，更复杂的示例如下:
matchThing = <text name="thing">
<text />
<sequence>
<first>
<class name="value"/>
<class name="function"/>
</first>
</sequence>
</text>
matchFunction = <text name="function">
<text />
<sequence>
<text name="input">
<text />
</text>
</sequence>
<sequence>
<text name="call">
<text />
</text>
</sequence>
</text>
matchValue = <text name="value">
<text />
</text>
它将匹配这样的文本:
<thing>
<call-me-anything />
<function>
<input><foo/></input>
<input><bar/></input>
<call><foo/></call>
<call><foo/></call>
<call><bar/></call>
<call><bar/></call>
</function>
<function>
<call><baz/></call>
</function>
<value>
<hello/>
</value>
<function>
<input><hello/></input>
<call><world/></input>
</function>
</thing>
因此，也可以将其想象为 JSON。
想知道你如何为此创建一个算法。我一开始就陷入困境，但它似乎需要某种类似递归下降的东西，但在树上而不是在序列上。
所以你有一个函数:
function checkIfMatch(actualTree, patternTree) {
for (node in actualTree) {
if (!checkIfMatchesSubtree(node, patternTree)) {
return false
}
}
return true
}
我真的不知道如何开始，正在 Google 上搜索“tree pattern matching algorithms”或“arbology”。如果我的方向正确的话，我将花费大量时间尝试将这些数学抽象转化为代码。想知道您是否可以帮助为这种情况构建一个简单的算法。很难弄清楚应该如何遍历实际的树，同时遍历模式树，并跟踪您在每棵树中的位置。
花相当多的时间在上面并没有让我走得太远:
function parse(patternTree, textTree) {
let state = { ti: 0, pi: 0 }
while (state.ti < textTree.length) {
let pattern = patternTree[state.pi]
let result = parsePattern(pattern, textTree[state.ti])
if (!result) {
return
}
}
}
function parsePattern(patternNode, textNode, state) {
if (patternNode.type == 'sequence') {
return parseSequencePattern(patternNode, textNode, state)
}
}
function parseSequencePattern(patternNode, textNode, state) {
while (true) {
let i = 0
while (i < patternNode.children.length) {
let childPattern = patternNode.children[i++]
let result = parsePattern(childPattern, textNode)
if (!result) {
return false
}
}
}
}
while (stack.length) {
let {
parents,
node,
} = stack.shift()
stack.push({
parents: [node, ...parents]
})
}
最佳答案
当尝试将模式 p 与树 t 匹配时，您必须首先将 p 的根及其子级与t 和 t 子代的根。如果 p 在根处不匹配，则必须遍历 t 的子级，并且每个子级值都与 p 匹配。
根据您发布的输入和节点类型，递归模式匹配函数必须处理三种主要输入场景:
p(对象)和t(对象)。在这里，模式是一个具有类型和子键的对象。输入树也是一个至少具有tag和children键的对象。模式匹配函数委托(delegate)给一个辅助函数，该函数对p的object.type进行匹配。p(对象)和t(数组)。在这种情况下，树是一个对象的Array，并且基于模式的对象，代码必须决定树的Array应该如何被处理(sequence、first等)。p(数组)和t(数组)。这里，p和t都是序列的形式，匹配操作就是查找，对于中的每一个的apArray，t的Array中对应的a1，使得pattern_match(a, a1)产生true。
首先，下面的代码实现了一个 find_match 函数，该函数支持基本节点 text 和 sequence:
//object that stores node match handlers
node_types = {'sequence':sequence_match, 'text':text_match}
//main find_match function
function find_match(pattern, tree_root, tree_children=null){
var tree = tree_children === null? tree_root.children : tree_children;
if (!Array.isArray(pattern)){
//pattern is an object - delegate to handler for node type
if (node_types[pattern.type](pattern, tree_root, tree)){
return true
}
//no match at the root - check the children
return tree.some(x => find_match(pattern, x, null));
}
//pattern is an array - delegate to sequence
return sequence_match({'children':pattern}, tree_root, tree)
}
//text match handler
function text_match(pattern, tree_root, tree_children){
if (!('value' in pattern) && !('name' in pattern)){
//empty text node found
return true
}
if (tree_root.tag === pattern['value' in pattern ? 'value' : 'name']){
//match found at the root - continue match with pattern and tree children
return find_match(pattern.children, null, tree_root.children)
}
//no match - check the tree's children
return (tree_children === null ? tree_root.children : tree_children).some(x => find_match(pattern, x))
}
//sequence match handler
function sequence_match(pattern, tree_root, tree_children){
var tree = tree_children === null ? tree_root.children : tree_children;
//copy the pattern and tree objects, as "p" is mutated as part of the match process
var p = JSON.parse(JSON.stringify(pattern))
var t = JSON.parse(JSON.stringify(tree))
while (p.children.length){
if (!t.length){
return false
}
var f = false;
var f_seq = p.children.shift();
for (var _n_t of t){
//compare sub-pattern and sub-tree
if (find_match(f_seq, _n_t, t)){
f = true
break;
}
}
//no match found for sub-pattern in sequence, return false
if (!f){
return false
}
}
//matches found for all sub-patterns in the sequence, return true
return true
}
tree = [{'tag': 'foo', 'children': [{'tag': 'bar', 'children': []}]}, {'tag': 'foo', 'children': [{'tag': 'bar', 'children': []}]}, {'tag': 'foo', 'children': [{'tag': 'bar', 'children': []}]}]
pattern = {'type': 'text', 'name': 'thing', 'children': [{'type': 'text', 'children': []}, {'type': 'sequence', 'children': [{'type': 'first', 'children': [{'type': 'class', 'name': 'value', 'children': []}, {'type': 'class', 'name': 'function', 'children': []}]}]}]}
console.log(find_match(pattern, {'tag':null, 'children':tree}))
//prints "true"
关于javascript - 如何在 JavaScript 中构建树模式匹配算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67441018/