Formula Trees

I dug out some old code that I originally wrote back in 1992 for solving equations. At the time it was command line based (remember command lines?) and I would dump the output to a text file. The text output would represent the original formula as a tree like this:

Node # 1|     0 : [ D ] <-  [ = ]  -> 3 : [ - ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 5 : [ / ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 6 : [ C ]

I'd then have to grab a pen and sketch things out to visualize it. I've always wanted to combine such programs with Flash and ActionScript. The screenshot is of my very first rudimentary attempt.

The code lets me select a variable from the formula and solve it. The way I do that is by manipulating the tree. Here's the output from the trace window:

solveFormulaFor( C )
moveFormulaTree()
... moving: -
Node # 1|     2 : [ A ] <-  [ = ]  -> 3 : [ + ]
Node # 3|     0 : [ D ] <-  [ + ]  -> 5 : [ / ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 6 : [ C ]
moveFormulaTree()
... moving: +
Node # 1|     5 : [ / ] <-  [ = ]  -> 3 : [ - ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 0 : [ D ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 6 : [ C ]
moveFormulaTree()
... moving: /
Node # 1|     4 : [ B ] <-  [ = ]  -> 5 : [ * ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 0 : [ D ]
Node # 5|     3 : [ - ] <-  [ * ]  -> 6 : [ C ]
moveFormulaTree()
... moving: *
Node # 1|     6 : [ C ] <-  [ = ]  -> 5 : [ / ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 0 : [ D ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 3 : [ - ]

The last set of nodes represents the solution that you can see in the lower part of the screen shot.

I still have a few kinks to work out of the code. It doesn't handle solving formulas with parentheses too well. I didn't realize there was a problem until I started visualizing it through Flash. Whenever I get around to fixing that and have a much cleaner prototype I'll post an interactive version.

I know quite a lot about calc engines. I used to work for Lotus testing 1-2-3 as well as another company testing their calc engine. Before that as a consultant I wrote code to parse and pull out data from spreadsheet files. I've also written calc engines based on an old simulation language called Dynamo. One day, if I can ever find the time, I may write an e-book on spreadsheet mechanics, or just my experiments with formula trees.

This is just the tip of the iceberg. I'm interested in manipulating and visualizing formula trees because the techniques can also be applied to one of my favorite topics - Genetic Programming.