Expression Parsing

A brief history

In MATH/CS 455 Numerical Analysis II, we used this cool thing called Horner's Method to reduce the number of operations needed to evaluate a polynomial expression. During my internship at Philips in Summer '22, I was bored and tried to implement that method in Python. Unfortunately, I was committed to solving the problem blind with no research or notes to assist me. After a dozen or so long nights brute forcing the problem, I gave up the project.

Current day

A week ago I was bored again and picked the project back up, this time taking the easy (smart) way and researching the algorithms I wanted to implement.

Before you can implement Horner's Method, you need to tokenize, parse, and simplify the expression. Tokenizing is very easy, parsing takes a little brains, but simplification (also referred to as rewriting rules or computer algebra) has been an open body of research since the 70s or earlier and is anything but simple.

I burned all my old code and rewrote the tokenizer and the parser so they actually work. Soon to be writing the simplification algorithm taking guidance from Joel Moses's 1971 paper Algebraic Simplification: A Guide for the Perplexed.

Stay posted.