What algorithm does Excel use to recalculate formulas?

Question

Are the formulas represented in a syntax tree then recalculated using a design pattern like the Visitor pattern? How would you go about reproducing the recalculation process in code?

Answer 1

Probably, as you say, one guess is that Excel creates a bunch of ASTs, one for each indipendent group of cells, where the leaves are the originating, static data, and the nodes are formulas.

Then it calculates the result for each node, with a post-order tree traversal algorithm.

You have to take into account leaf/node cancellation, partial recalculation, ecc. If I'm not wrong, I read somewhere that Excel could benefit of multicore processors to recalculate a sheet in parallel.

Answer 2

Resolver One was a spreadsheet developed using IronPython.

Its source code has been released as Dirigible Spreadsheet. There used to be an article that described its overall algorithm:

Answer 3

Are the formulas represented in an AST then recalculated using a design pattern like the Visitor pattern?

You're thinking interpreter, not visitor. While treewalking using a visitor can be employed in conjunction with interpretation, employing an interpreter makes more sense here (hence the name). What this does is basically what friol wrote, i.e. traverse the tree in post-order and execute the function associated with each node.