Алгоритм преобразования из выражения в представление графа (DAG)

Question

Я читал об алгоритмах объединения, и эффективные, кажется, имеют в качестве входных данных DAG, где, как я понимаю, термины, которые являются общими в выражении, не являются дублированными узлами (как в AST).

Я уверен, что есть хорошо известные алгоритмы, которые преобразуют выражение из "строкового представления" или AST в DAG. Существуют ли такие алгоритмы? Я просто хочу не изобретать велосипед.

Answer 1

Это легко сделать с помощью памятки при построении AST.

Поскольку AST встроен в порядок заказа, при создании каждого узла проверьте кэш памятки, чтобы увидеть, существует ли уже эквивалентный узел.Если это так, используйте уже существующий узел.В противном случае используйте новый узел и добавьте его в кеш.

При проверке кеша на наличие ранее существующего узла дочерние элементы этого узла уже будут запомнены, поэтому вы можете сравнивать их по тождеству, а не пересматривать их подграфы..