Precedence: Chapter 4

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:

public interface SyntaxTree {
  int evaluate();
}

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:

public static class Number implements SyntaxTree {
  private final int value;

  public Number(int value) {
    this.value = value;
  }

  @Override
  public int evaluate() {
    return value;
  }
}

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:

enum OpType {
  plus(1, "+"),
  minus(1, "-"),
  multiply(2, "*"),
  divide(2, "/");

  final int precedence;
  final String opString;

  OpType(int precedence, String opString) {
    this.precedence = precedence;
    this.opString = opString;
  }

  public static OpType fromString(String token) {
    for (OpType type : values()) {
      if (type.opString.equals(token)) {
        return type;
      }
    }
    throw new UnsupportedOperationException("invalid op type token " + token);
  }
}

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:

public static class Operation implements SyntaxTree {

  private final OpType type;
  private final SyntaxTree left;
  private final SyntaxTree right;

  public Operation(OpType type, SyntaxTree left, SyntaxTree right) {
    this.type = type;
    this.left = left;
    this.right = right;
  }

  @Override
  public int evaluate() {
    int l = left.evaluate();
    int r = right.evaluate();

    switch (type) {
      case plus:
        return l + r;
      case minus:
        return l - r;
      case multiply:
        return l * r;
      case divide:
        return l / r;
    }

    throw new UnsupportedOperationException("unknown error!");
  }
}

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:

public static SyntaxTree parse(String expr) {
  String[] parts = expr.split(" ");

  SyntaxTree tree = new Number(Integer.valueOf(parts[0]));
  for (int i = 1; i < parts.length; i += 2) {
    OpType opType = OpType.fromString(parts[i]);
    tree = new Operation(opType, tree, new Number(Integer.valueOf(parts[i + 1])));
  }
  return tree;
}

And that’s it.

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

public static void main(String[] args) {
  SyntaxTree tree = parse("5 + 4 - 9 * 16 + 44 / 2");
  System.out.println(tree.evaluate());
}

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:

Operation applyPrecedence() {
  if (left instanceof Operation) {
    Operation l = (Operation)left;
    l = l.applyPrecedence();
    if (l.type.precedence < type.precedence) {
      return new Operation(l.type, l.left, new Operation(type, l.right, right));
    } else {
      return new Operation(type, l, right);
    }
  }
  return this;
}

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

public static SyntaxTree parse(String expr) {
  String[] parts = expr.split(" ");

  SyntaxTree tree = new Number(Integer.valueOf(parts[0]));
  for (int i = 1; i < parts.length; i += 2) {
    OpType opType = OpType.fromString(parts[i]);
    Operation op = new Operation(opType, tree, new Number(Integer.valueOf(parts[i + 1])));
    tree = op.applyPrecedence();
  }
  return tree;
}

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!

Jon Bedardprecedence