During my second year of undergraduate studies in TAU we had to write a symbolic calculator for our second year software project, a basic exercise in writing software with emphasis on text parsing. The input was a parenthesized expression, from which we had to create the appropriate (mathematically balanced) expression tree and evaluate it. The common way to read the expression and create expression tree was to use two stacks (one for operands and one for the operators). However, I created a new algorithm to accomplish this task in linear time. At the time we learned in another course about tree rotations methods, as mentioned in Cormen’s Introduction to Algorithms. Tree rotation are commonly used to balance search trees. I decided to adopt these methods and use them to re-balance the expression trees into their correct form. The algorithm reads the expression as is to a one sided binary tree and using rotate operations balances the tree to its mathematically correct form. The entire operation is extremely efficient and is linear to the size of the input. It’s important to note that the traditional stacks-based way to parse such expressions is also linear. Thus, my choice of solution didn’t present a significant improvement, it was just a different way to do things which I wanted to explore. A more detailed explanation of the algorithm and an example is available in the short documentation below.
Short documentation of the algorithm [PDF]
The full documentation of the symbolic calculator [PDF]
The entire code is available upon request.