[ Home ] [ Up ] [ Assignment 6a ] [ Assignment 6b ] [ Assignment 6c ]

Abstract Syntax Trees

Part C: Teaching walk() to Correctly Parenthesize

You probably noticed in Part B that there are certain expressions (such as the second and third expressions in our enhanced Tree class) where the output isn't quite right -- it needed extra parentheses to represent the correct operator precedence.

Let's fix this. Here are the steps we'll follow:

• Modify the Operator class as follows:
  • Add a set of public static final data members (why static and final?) of type int, to indicate various operator precedence levels:
    PREC_HIGHEST, PREC_HIGHER, PREC_MEDIUM, PREC_LOWER, PREC_LOWEST
    Note that the actual values of these data members don't matter, except that the values should represent the relative precedence values appropriately. I suggest that PREC_LOWEST be assigned a value of 0, and that you increase the value by 5 or 10 for each precedence level above that. That way, if you later needed to insert an additional precedence level, you have room to do so.
  • Add a protected abstract method getPrecedence() to force every class that extends the Operator class to implement this method.
• At this point, if you build your classes again, you'll find that they won't build -- they generate errors. To solve this, you'll have to add an implementation of the getPrecedence() method to every concrete class that extends Operator.
  • Have each method return one of the values defined in Operator (and remember that Operator is a superclass)
  • The UnaryPlus and UnaryMinus classes should return PREC_HIGHEST, the Times and DividedBy classes should return PREC_HIGHER, and the Plus and Minus classes should return PREC_MEDIUM
• Once you've implemented all these getPrecedence() methods, the entire thing should build again. However, we haven't actually used the methods anywhere, so the behavior of our classes will be as it was before. So, let's finish the job:
  • In each of the walk() methods you'll have to do the following:
    • For each operand, find out whether the operand is an Operator. How? 

    Hint: There's a convenient operator to do this.

    • If it is an Operator, compare its precedence level with the precedence level of the current operator.
    • If the precedence level of the operand operator is lower than that of the current operator, insert parentheses around the walk() call for that operand.
• That should do it! Rebuild, and try it.
  In my implementation, the second and third expressions printed out as:

Result of 53.5 / 45 - 73.54 * (+3 + 8) = -807.7511111111112
Result of (53.5 - 45) * (73.54 + -3 + 8) = 667.59

This page was last modified on 02 October, 2007