CIT594 Tree.parse

CIT 594 The Tree.parse(String) method
Spring 2008, David Matuszek

A lot of people lost points on the parse(String) method in the Tree class. Because this method is important, I'm giving you a chance to make up those lost points.

First I'll tell you why I think it's important, then I'll tell you how to get points back.

A well-tested program will have fewer bugs than a poorly-tested program. So you should write lots of good tests. If testing is difficult, you won't write as many tests. If it's easy, you'll write more tests (and probably better ones). So it's important to make it easy to write tests.

Here's how you can construct a tree without the parse(String) method:

Tree aTree = new Tree("a");
Tree bTree = new Tree("b");
Tree cTree = new Tree("c");
Tree dTree = new Tree("d");
Tree eTree = new Tree("e");
Tree fTree = new Tree("f");
Tree gTree = new Tree("g");
aTree.addChildren(bTree, cTree);
bTree.addChildren(dTree, eTree);
cTree.addChildren(fTree, gTree);

And here's how you can construct the same tree with the parse(String) method:

Tree tree = Tree.parse("a ( b(d e) c(f g) )");

Here's an example test from my ParserTest class, just to show how simple testing can be:

@Test
public void testIsLineAction() {
    use("line 1, 2, -3, 4.0 \n");
    assertTrue(parser.isLineAction());
    assertStackTopEquals("line(1.0 2.0 -(3.0) 4.0)");
}

Unfortunately, there's a bit more to it than just writing the parse method, because the parse method creates a tree of Strings, not a tree of Tokens. Here's what I did about that:

In my Token class I added a constructor that took just a String as an argument (instead of a String and a Token.Type), and called determineTokenType(String) to figure out the type.
I wrote the determineTokenType(String) that figures out the token type (in some cases, from just the first character). 15 lines.
In my ParserTest class, I wrote a simple recursive method, Tree<Token> makeTreeOfTokens(Tree<String> treeOfStrings), to create a tree of Tokens from a tree of Strings. 10 lines.

You don't have to write these methods yourself, but if you do, it will simplify your remaining testing.

A good parse method makes it much easier to construct complex trees for testing purposes. However, complex trees require lots of parentheses, and it's very easy to get them wrong. Not only might you have unbalanced parentheses, but you can also write balanced but incorrect expressions, for example, "one two" or "=( (+ 2 2) 4 )". If your parse method fails silently for these, it will make testing much harder.

For that reason, my JUnit tests for parse require that it throw an exception (of any sort) when given ill-formed input. These exceptions have saved me a lot of trouble as I wrote the Parser, and I expect they will continue to save me trouble as I write the Interpreter.

If you've suffered through the above sermon (or even if you haven't), here's the deal. Turn in your Tree class with a corrected parse method by Friday midnight, and you can get back the points you lost on this method. This is a hard deadline--after Friday midnight, you've lost your chance to get points back.

We will test your program with my TreeTest.java class, so you may want to download this file.

Since you will be using the Tree class for the next two assignments, it wouldn't hurt to make any other necessary corrections, but I'm only offering make-up credit for the parse method.