CS Labs: Lab 15

CS Labs: Lab 15


To accompany Chapter 15 of An Introduction to Object-Oriented Programming with Java by C. Thomas Wu.

Read the documentation for Lab 15

There are 8 checkpoints in this lab. If you need help with any exercise, raise your hand.

Copy the lab materials to your account by entering

             cp -r /home/Classes/Cs1/Labs/Lab15 .
     
Everything you need for the lab exercises today is contained in this new directory.

Checking for Odds and Evens

Change into the OddEven directory and examine the Demo class. All the methods in this class are static. (What is the implication of this?)

The code for isEven() is not complete. Finish this code, following the example for isOdd(). Remember that zero is an even number and that any number x is even (or odd) if and only if the number x-1 is odd (or even).

The isOdd() and isEven() methods are called mutually recursive because each one calls the other. Contrast this with the factorial() method in your book; factorial() is directly recursive because it calls itself. Both are examples of recursion.

Compile and run the Demo program and test it with several integer values. The input values for your program should come from the command line, as in

java Demo 0 1 2 5 42 43
Use this list of values for at least one of your tests.

Un-comment the debugging lines in the isOdd() and isEven() methods, recompile and run your program with the test values give above. Observe that larger values produce more debugging output.

1 Explain why all the methods in this class are static. Show us your debugging output, and explain why larger integer values produce more output.

Put the debugging comments back in your program and recompile it. See if you can make your program fail when you run it with a large positive integer value (but less than 2 billion). Draw a diagram similar to Figure 15.8 in your book to illustrate what might be happening.

What happens if you run your program with a negative integer value such as -1? Try it. Draw a diagram of recursive calls to illustrate what might be happening.

2 Explain why a large positive integer value makes your program fail. Show us your diagram of recursive calls to support your conclusion. Do the same for a negative value.

Modify your program by adding a testOdd() method that will produce output similar to the testEven() method. Change your main program to call testOdd() instead of testEven(). Compile and run your program with sample integer input values of your choosing.

3 Show us your modified program and sample run.

Modify your testOdd() method so that it determines directly if its integer parameter is odd or even by replacing the call to isOdd() with a simple (non-recursive) calculation involving the modulus operator %. Your program should work properly with large positive integers and with negative integers as well.

4 Show us your modified program and sample runs.

A's and B's

Change into the AB directory and examine the Demo class. To create an instance of this class, you pass a String object to the constructor. An integer variable loc stores the location in the string of the "current chracter". The constructor initializes this variable to zero, so that the "current character" starts out being the character at the beginning of the string.

The peekChar() method returns the character at the "current character" position. The hasMoreChars() method returns true if loc refers to a character actually in the string, and false otherwise. The nextChar() method acts like peekChar(), except that it advances the "current character" to refer to the next character in the string.

Any attempt to call nextChar() or peekChar() when there are no chracters remaining in the string will raise an exception.

We are interested in determining whether a given string consists exactly of any number of as followed by the same number of bs. For now, we'll call such strings legal. The parse() method examines the string, checking (through calls to match()) that the string starts with a and ends with b and -- here's the recursive part -- that the rest of the string (excluding the beginning a and ending b) also has the same structure.

The checkAB() method first calls parse(). If parse() succeeds without an error (i.e., without throwing an exception), the string is legal (a bunch of as followed by the same number of bs) if there are no more characters remaining in the string.

Compile this program. As with the OddEven example, you should provide the strings to test on the command line, as in

java Demo a ab abb abba abab aaaaaaaabbbbbbbb abc cab
Examine these test strings and determine which of them are legal (as described above). Run the program with the tests given here and compare your results with what you expected.

5 Show us the strings you determined to be legal and the results of running your program.

Now let's change the definition of what strings are legal. For example, suppose we want to identify all strings that consist exactly of any number of as followed by twice as many bs. Modify the parse() method to do this. You will need to add only one line.

Compile and run your program with test data of your own design.

6 Show us the line you added to your code. Demonstrate your running program and your test data.

Remove the line you added for the previous checkpoint so that your program will again check for an equal number of as and bs.

Notice that your parse() method did not actually count the number of as and bs. Instead, it kept track of them implicitly through recursion!

Modify your parse() method so that instead of being recursive, it counts the number of as and bs in two integer data variables a_count and b_count (suitably initialized to zero). Do this in a while loop as long as there are more characters in the string.

In the body of the loop:

After you call parse() in checkAB(), indicate a parse error if there are more characters in the string or if a_count and b_count are unequal. Otherwise, indicate that the parse was OK.

7 Show us your modified code for parse() and checkAB(), and your running program.

After the Lab

8 Show us that you have logged out, cleaned up, and pushed in your chairs for this last checkpoint.

End of Lab


Susan Haller and Timothy Fossum, University of Wisconsin-Parkside