Проходим дерево снизу вверх и, включая дедупликацию узлов
Алгоритм
/** Узел исходного синтаксического дерева */public interface ParseNode { /** * Имя операции или идентификатор/константа */ String op(); /** * Дети (может быть пустым списком) */ List<ParseNode> children();}
import java.util.*;public final class DagNode { private final String op; private final List<DagNode> children; public DagNode(String op, List<DagNode> children) { this.op = op; this.children = List.copyOf(children); } public String op() { return op; } public List<DagNode> children() { return children; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof DagNode node)) return false; return op.equals(node.op) && children.equals(node.children); } @Override public int hashCode() { return Objects.hash(op, children); } @Override public String toString() { return op + children; }}
import java.util.*;public final class DagBuilder { /** Таблица уникальных узлов DAG */ private final Map<DagNode, DagNode> unique = new HashMap<>(); /** * @param root синтаксическое дерево */ public DagNode build(ParseNode root) { return buildRecursively(root); } private DagNode buildRecursively(ParseNode node) { // Рекурсивно строим DAG для всех детей List<DagNode> childDags = new ArrayList<>(); for (ParseNode child : node.children()) { childDags.add(buildRecursively(child)); } // Создаём узел-кандитат в DAG DagNode candidate = new DagNode(node.op(), childDags); // Проверяем есть ли уже такой узел DagNode existing = unique.get(candidate); if (existing != null) { // используем существующий узел return existing; } // Добавляем узел-кандидат в таблицу unique.put(candidate, candidate); return candidate; }}
