Какой алгоритм использует Excel для пересчета формул?

Вероятно, как вы сказали, одно предположение состоит в том, что Excel создает набор AST, по одному для каждой независимой группы ячеек, где листья — это исходные статические данные, а узлы — это формулы.

Затем он вычисляет результат для каждого узла с помощью алгоритма обхода дерева post-order.

Вы должны учитывать отмену листа/узла, частичный пересчет и т.д. Если я не ошибаюсь, я где-то читал, что Excel может использовать многоядерные процессоры для параллельного пересчета листа.

Resolver One — это электронная таблица, разработанная с использованием IronPython.

Его исходный код был выпущен как Dirigible Spreadsheet. Раньше была статья, в которой описывалось его общий алгоритм:

Формулы, представленные в AST, затем пересчитываются с использованием шаблона проектирования, такого как шаблон «Посетитель»?

Вы думаете об переводчике, а не о посетителе. В то время как обход дерева с использованием посетителя может использоваться в сочетании с интерпретацией, использование интерпретатора здесь имеет больше смысла (отсюда и название). То, что это делает, в основном то, что написал friol, то есть проходит дерево в обратном порядке и выполняет функцию, связанную с каждым узлом.