I’d like to start by stating how I don’t usually do many tutorials like this, where it’s purely theoretical & it’s very unlikely that you’d want to be doing this yourself in the real world. But I found myself wondering & I thought heck, why not give it a go? So here we are.
One dull day, I was at work & sadly it was the kind of day where it involved a lot of meetings & little code was written. Being the way that I am, my brain went off into thinking about refining my skills & practicing, I’m a firm believer that even the most talented of software engineers should practice whenever they get a chance. Not to say that I think I’m one of the most talented software engineers, not by any stretch of the imagination, I mean I wouldn’t trust myself writing code in C/C++, at least not right now anyway. That’s one thing that I want to personally improve upon, learning & studying lower-level programming languages.
Huh, wouldn’t it be fun to implement an algorithm that evaluates mathematical expressions, but none of this kiddy script stuff, one that uses real principles like BODMAS.My Brain
The code that I’ve written is by no means battle tested, I’ve not tried it with a load of different formulas to verify that it’s ready for the real world. This was purely & totally an experiment for fun, in the real world I would use a third party library that’s well supported. For the simple reality being that you wouldn’t want to maintain something like this yourself if you’re working on some customer facing product. That would be insanity at its finest.
There’s a good chance that there are some bugs in this code, but I thought it might be fun to share how I thought about the problem more so than the solution itself. I also know that I’ve not gone all out with the validation side of things, so it’s very likely that you could easily break the algorithm by feeding it some invalid expression. I did consider writing a guard for this, but then I thought ah, that might be going too far down the rabbit hole. Might be fun to leave that to other people, people who might be a lot smarter than me.
I also wanted to clarify, this is more of a walkthrough about my thought process as opposed to it being a tutorial, but I’m not going to get all pedantic on the terminology I’ve used. I thought this post might be a bit of fun, maybe insightful to some, etc. I just hope you enjoy the content & my general thought process.
The Thought Process
I started thinking about how some basic maths fundamentally works, in an abstract sense anyway. I went on to think along the lines of how a bracketed expression is like a context, but it also reminds me of a tree node, where it can have one or many children, the overall expression itself is like one big unbalanced tree. For each bracket, it contains some sub-expression that needs to be calculated before you progress outwards, nearing the overall answer.
Now that I have a clear data structure in mind, I just needed to essentially build some kinda parsing function to parse the string into this data structure, which I found to be a lot more simplistic than what I would’ve initially thought in all honesty. Which then got me on to thinking about how mathematical formulas are written as strings, how I’d need some sort of buffer involved, i.e. if you were to use a negative number or use a large number, you’d want to append some values to a buffer before you specify that a value is in some valid or complete state. It would be too easy to have some parser that only recognises numbers & operations.
So this thought process took me to this solution:
I’m by no means precious about this solution I just know that it’s really simple & it works, I didn’t implement this solution in hope of it being the most performant code on earth, nor did I aim to make it a work of art. Quick & messy is exactly what the doctor ordered.
As you can see, for every instance we come across a new parenthesis, we work out where the matching closing parenthesis is. From there, we create a substring to get the nested expression & then we create a node for our tree data structure with this expression.
We keep track of the current node, the current will essentially change what level it is sat on within the data structure as the parenthesis open & close. It might not be the most scientific or elegant approach ever, but it simply works.
As you can see, there’s little to no validation with this parsing code, and there’s a load of things that we could do to implement validation, but as previously mentioned, I didn’t want to totally neglect my day job thinking about all the potential hacky ways people could abuse this algorithm.
Tree Node Calculation
Now that I’ve teased you a little with showing how I thought about the parsing of the given equation. I think it’s only fair that I now show you how I thought about the calculations side of things with regards to the tree node itself. The rational thought process being that you want to do the nested most calculations first & then work backwards, back to the root of the tree data structure.
As you can see, in my brain, I tried to break it down into really simple terms, thinking about breaking a given expression into chunks, where each chunk consist of a left value, a right value & an operator sat in the middle. As we work from left to right, while using the rule of BODMAS, we calculate the value for the tree node. We store the value in the answer property on the tree node & this becomes very relevant much later on.
You might’ve noticed how I decided to implement a parser for the tree node itself, I thought about how I first want to create an array of all of the components of the expression, for example -77 would be its own part, then each operator would be its own part also. Etc. It just made it really simple in my head to do it this way.
You might have also noticed that I did decide to implement some pretty fundamental validation here. Just as a bit of a sanity check & in all honesty, I did this to show where I might have been going wrong when I was developing the solution.
So, once we’ve built up an array of parts, we want to ensure that we clear the buffer that we were initially using to build up the array of parts. Now that we’ve build our array of parts to our expression, we also want to break this apart into chunks. The idea being that the chunks will consist of three simple properties, a left value, a right value & an operator. I think you can see where I was going with that thought process.
But as we compute the calculation(s) or the answer for a given node, we want to be updating neighbouring chunks. That way as we work through the chunks, we have a valid result at some point as we continue to progress with our algorithm.
Now that I feel like we’ve got the hard part out of the way, I thought that it would only make sense to make all of the nodes within the tree play nicely together. I wanted to now figure out a way to work backwards, my solution is actually insanely simple & ironically massively inefficient. Given that I had more time to think about this, there are some real easy ways to optimise this, not just in terms of computational complexity but also in worrying about memory allocation & so on.
I thought about how I had done all of the “hard parts”, no just reap the rewards, be lazy & simply work from the top down, replacing the expressions in the original expression with the values provided by the tree nodes. Granted, there’s probably a much better way to do this without giving it too much thought, but I really wanted to keep this code relatively concise. Again, I’m not proud of this code, I don’t like how nested it is & so on, but it works. I honestly wanted to write this in as little time as I possibly could.
If you’d like to see my complete example, you can find it here. Again, I thought that this little mental walk through about how I thought about a theoretical problem & what kinda steps I took to resolve the problem. Again, this code isn’t production ready, please don’t use this code in the real world, it really is just here as a little tutorial & walkthrough, nothing more, nothing less.
I’ve also mentioned AI a few times in my previous blog posts, ironically this is a prefect example of where AI sucks. I tried to use GitHub Copilot, ChatGPT & a few others to help me write the code to provide a more performant & solid solution. Instead, they all produced some horrifically buggy code in some form or another, it ironically just dampened progress as I was looking at the code the ML models were spitting out & trying to study them, trying to make sense of what it is they were doing. When I couldn’t quite work it out, as it looked fundamentally incorrect to me, I ran the code it spat out & what would you know? The code didn’t work. I actually thought it was just me being the problem, having a hard time to make sense of the code that the model(s) were producing. Even ignoring the BODMAS rule, a simple calculator, it would struggle massively to produce anything that would work. I think this just reinforces my theory that AI currently struggles with context & understanding rules, etc. Even something as old & well defined as the world of Mathematics.
I don’t like to be negative towards AI, I really want to see it develop, there’s a ton of cool things that you can do with AI today, like generating digital art. That’s an awesome little tool to use, but when it comes to software engineering, anything beyond a simple crud application, I really do believe that it has a long way to go before it can be used by engineers.