Finally, We Write Some Code

I’m going to attempt to create the most minimal program that will demonstrate our problem. For this, I’ll use Java, but the concepts would be the same in any language.

Let’s start by modelling our Syntax Tree:

Our syntax tree will be used for the sole purpose of evaluating simple math expressions, hence the simple interface. Next, we can add our first concrete type, a Number:

And as we mentioned before, when you evaluate a Number, it simply returns itself.

Modelling Operations

Now it gets a bit more complicated. We’ll need the concept of an operation, such as 1 + 5, or 112 * 13. The operator has a limited set of operations, so an enum works well:

You see we’ve provided a little additional information here. For one, we’ve added the ability to get an OpType by its String version. This will be helpful during parsing. Next we’ve added the precedence of the operation. This information will come in handy when we fix our bug :-)

Alright, now that we have an operation type, we can model the operation itself. Here’s what it looks like:

An Operation is the operator type and the left and right subtrees that are operated upon. They may be simple numbers, or they may be entire trees, but it doesn’t matter from the Operation’s perspective.

Our evaluate routine is also pretty straightforward. We just have to check what type of Operation it is, and then do the associated math.

Parsing Math Expressions

Now let’s write a parser for our mathematical expressions. We’ll focus on simple math expressions of the form: num op num op num. We won’t worry about error checking or anything like that:

And that’s it.

Alright, we have all of our players, let’s see what happens when we run this:

22! Yay! Oh wait, that’s terrible. That’s not the correct answer at all. Not even close. The correct answer is -113. We weren’t even on the right side of 0. Embarrassing.

Apply Our Fix

Well, luckily, we know the trick to fixing it. Whenever our left subtree is a lower precedence, we need to “rotate” our tree clockwise. Refer back to our animations from Chapter 3 if you need a refresher on how this happens. Once we’ve completed this rotation, the lower precedence operator will be higher in the tree and as a result will be calculated later. So what does that look like in code?

Let’s add a method called “applyPrecedence” to our Operation class:

And let’s make sure to call that method whenever we parse an Operation. I’ll rewrite the entire parse method for clarity:

All of that code was the same as before, except now we are calling the method whenever we create a new Operation. So let’s run our code again: -113! The correct solution!

Conclusion

So ends the tale of our precedence bug. It’s been a long and winding road, but I hope you had as much fun reading about our bug as we had fixing it!

Stay tuned for more posts about INH, as it’s a constant source of great programming stories!