Recently, I was looking at ways to analyze Excel formulae to express them as SQL queries. I originally experimented with Regular Expressions but this quickly became too verbose and complex. It then occurred to me that if I was working with formulae then the right approach would be to use an expression parser.

I really did not want to write a parser from scratch, so I went hunting in the Web for something already built. Eventually, I landed on a Stack Overflow answer to a question very similar to mine. One of the responders and pasted in his implementation of ‘Dijkstra’s Shunting Yard Algorithm’ – probably the result of a Computer Science assignment from many years ago.

Now the code was incomplete. It missed supporting classes and it did not deal properly with functions of differing argument counts. Nonetheless, I grabbed it, refactored it and re-engineered it to fit my needs. But there was a hidden gem in his solution. He had expressed the output as a binary tree of objects representing the operators, functions and operands. I soon realized that I could easily search this tree to find all the pieces to solve my original problem.

That’s the true value of sharing code. Had this contributor not presented his code (incomplete or not), then not only would I have had to reimplement my own version from scratch, but I most likely would not have thought of using a binary tree to capture the expression. Then I would have had to write a lot more code to search for terms.

Thank you, Evil Penguin (https://stackoverflow.com/users/193486/theevilpenguin) from Australia and everyone else who posts answers and code snippets on the web.

Share Button

Related Post

Leave a Comments