匹配类型层次结构

Question

假设我们有一个固定的类型层次结构，例如如下所示。它是一棵定义明确的树，其中每个节点都有一个父节点（根除外）。

每种类型都有与之关联的操作，应在成功匹配后执行。但这并不意味着一个动作对应于该类型的方法。这只是任意关联。

将对象与类型层次结构匹配的智能方法是什么？每个对象都应该与最具体的类型进行匹配。对象已经创建。

Answer 1

使用从根开始的递归搜索。

一旦在children中找不到匹配项，如果匹配对象的级别比上一个匹配项更深，则记住该匹配对象。

伪代码：

    class MatchContext {
         public int level;
         public Node result;
    }

    public boolean match(Node object, int level, MatchContext ctx) {
        if (no match)
            return false;
        boolean found = false;
        for (all children in object) {
            if (match(child, level + 1, ctx))
                found = true;
        }
        if (!found && level > ctx.level) {
            ctx.level = level;
            ctx.result = this;
        }
        return found;
    }

像这样调用它：

    MatchContext ctx;
    if (match(root, 0, ctx))
        myAction(ctx.result);