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.
Lance is VP of Engineering at Submittable where he helps build software that writers and publishers around the world love to use. Lance occasionally teaches and presents at the University of Montana and Montana Code School. He lives with his wife and two sons in Missoula where he’s often found running on trails in the forest and on top of mountains.