Let's Build a Spreadsheet with Algorithms
First, we’ll build a parser and interpreter to understand formulas like `SUM(A1:B5)` or `AVERAGE(SUM(A1:A5), SUM(B1:B5), SUM(C1:C5))`. We’ll cover the basics of lexical analysis, abstract syntax trees, and the visitor pattern for walking trees.
After we have an interpreter, we’ll build the calculation engine to find the values for all the cells. We’ll represent cell references as a directed acyclic graph (DAG). Finally, we’ll implement a topological sort on the graph to determine the order of cell evaluation, and run our interpreter to calculate values.
The presentation is for more experienced developers. However, no experience with standard algorithms or compilers is needed. This is designed to be in introduction to both topics. Source code will be available as an open-source repository on GitHub.