Problem Solving in Java, Part I

Abstract

The past labs involving Java have examined some mechanics of Java classes and objects. This reading takes a fresh look at the role of these classes and objects in solving problems. Through the discussion, the reading also considers how simple input might be handled within Java and introduces the syntax for conditionals and some loops in Java.

The Role of Classes and Objects in Java

As you have seen, all work in Java is based on classes and objects. That is, Java packages all data and operations into classes. For example, code that would be a "main program" in other types of languages is designated as a

public static void main

method of a class in Java. For most other work, data and operations are grouped together in a coherent way to make natural packages. For example, the java.io package contains the PrintWriter class that we have used for output.

With this wealth of class definitions available, efficiency of problem-solving may be enhanced greatly if you can identify classes that may be relevant to a problem. As you encounter new classes, therefore, you should review their capabilities (i.e., concept and methods), so you will know the operations that are built into existing classes. In a well written class, you need not concentrate on the details of how the methods work in order to use those methods. Rather, comments and a method header may be adequate to learn what the method does and how it may be invoked.

Documentation on all pre-defined Java classes is available from http://java.sun.com/j2se/1.4.2/docs/api/index.html. The main page contains an index of both the main packages and the main Java classes; you may click on any package or class for details on that individual class. You may want to bookmark this site in your browser for further reference!

Example: Piles of Magazines and Bills

In a previous lab on object-oriented programming, we studied a stack as a simple example of a class or abstract data type. In that lab, a stack contained the following operations:

• Make-Stack
  Create a new, empty stack object.
• Empty
  Empty returns true or false (#t or #f), depending upon whether the stack contains any items or not.
• Push
  Push adds the specified item to the top of the stack.
• Pop
  If the stack is not empty, Pop removes the top item from the stack, and this item is returned.
  If the stack is empty, nothing is returned, and an error is reported.
• Top
  If the stack is not empty, the top item is returned, but the contents of the stack are not changed.
  If the stack is empty, nothing is returned, and an error is reported.

An example then defined a stack class in Scheme, created two stacks, mag-pile and bill-pile and performed a sequence of push, empty?, pop, and top operations.

In Java, it turns out that a Stack class is already available as part of a utility library. To examine the methods of this class, go to the on-line documentation at http://java.sun.com/j2se/1.4.2/docs/api/index.html, as described above. Then scroll through the index of classes to find documentation on the Stack class. Double click on Class Stack to examine the built-in Stack class.

In the Methods sections of the documentation, you will see that this Stack class does not contain an operation top. Can you find another method that seems to do the equivalent operation?

With the definition of a stack class already done, we can follow the same steps of the previous Scheme example by adding an appropriate class framework:

1. Create a class StackExample to provide a place for our simulation.
2. Import the existing Stack class,
3. Import the PrintWriter class for printing,
4. Create a main method for the main steps of our example,
5. Within main, create appropriate stack and output objects, and
6. Translate operations of the example from Scheme to Java.

While this translation involves some overhead, the Java code follows the previous simulation closely. File StackExample.java in package stacks shows the resulting program.

Reading Integers in Java

Reading numbers from the keyboard is inherently somewhat complex, because it involves several steps:

1. a user presses keys that generate character data;
2. the computer must combined successive digits into a logical unit;
3. the character string of digits must be translated from a string to a numeric value.

Various langauges approach this task in different ways. Since Scheme does not require a programmer to designate the types of variables, Scheme's read procedure infers the type of data being ready as it goes along. Thus, if the first character that Scheme encounters is a digit, then Scheme expects to read a number, so it reads successive characters as part of that number, and converts those characters to the appropriate type of number. In contrast, if Scheme's read procedure first encounters a left parenthesis, then Scheme infers that a list will follow, and Scheme continues reading until the end of the list.

In contrast, as a typed language, Java expects the nature of data to be known in advance. Further, since a user will always be entering characters, the basic form of input must be a string. When an integer value is desired, the programmer then must convert this string to an integer value. One implementation of this approach involves the BufferedReader class to read the string and the Integer class to handle the conversion.

The BufferedReader Class

Just as PrintWriter is a common Java class for output, many programs use class java.io.BufferedReader for simple input. As shown in the documentation, read() returns a single character, while readLine() returns an entire line as a string. Since much input requires more than one character, readLine() is often used.

One special feature of BufferedReader is that a program may specified a point, called a mark, in reading. Later, one can return to that point with a reset() method −− until reading has progressed beyond a specified distance beyond the mark.

When using BufferedReader, declarations and initialization typically proceed as follows:

   java.io.InputStreamReader istream = new java.io.InputStreamReader(System.in);
   java.io.BufferedReader in = new java.io.BufferedReader(istream);

After initialization, the method invocation in.readLine() handles the input chores:

   String line;
   ...
   line = in.readLine();

As a detail, note that readLine anticipates that some circumstances might arise for which reading fails. In this case, readLine() throws an IOException. We will talk about such exceptions later in this course. For now, we let the Java environment handle such matters. This is why we include the words throws Exception in the header of the main method where readLine is used.

Conversion From a String to an Integer or int

Once the variable line contains a string of digits (e.g., "1432"), a program must convert the string to an Integer object or to an int type to perform numeric processing. The Integer class provides methods to support this work:

• The expression new Integer (line) use a constructor for the Integer class to create a new Integer object, initialized by the string line.
• The Integer class includes a method intValue() that returns an int value.

Putting these pieces together, the following translates the character string line to an int.

int value
...
value = new Integer (line).intValue();

Approximating Pi

A second use of classes is seen in the following application to approximate Pi.

Problem

Consider a square of side 2 in the plane, centered at the origin, so the square extends one unit along each axis in each direction.

Suppose a point P is picked at random in the square. What is the likelihood that P also will be within a circle of radius 1, centered at the origin?

Discussion

Mathematically, the desired probability depends on the relative area of the circle and the square. Since the circle and square have radius 1 and side 2, respectively, their areas are Pi and 4, respectively. Putting this together gives the following:

Probability (P in circle) = Area Circle / Area Square = Pi / 4.

A similar analysis applies if we restrict P to the first quadrant.

Applying this to an experiment, we might pick N points at random in the square in the first quadrant. We then could count the number I of points inside the circle. We would expect that

I / N = (approx) Pi / 4.

Solving for Pi gives

Pi = (approx) 4 I / N

To use this estimate in a program to approximate Pi, we need to be able to create random points in the square, determine their distance from the origin, and count if they are in the circle. This work is done in the following outline:

Code Outline

1. Read number N of points to be selected.
2. Set counter to 0.
3. Repeat N times:
   1. Create a point P in the unit square in the first quadrant.
   2. Check if P's distance to the origin is less than or equal to 1.
   3. If so,increment counter by 1.
4. Print number of times point was in circle.
5. Print estimate of Pi by the formula, Pi = (approx) 4 I / N.

Implementing the Outline

In implementing the outline, we first consider what properties we need for points. In the outline, we must create points and determine how far they are from the origin. One simple approach for this task is to declare variables x and y as double precision real numbers. Given such a point, its distance from the origin is sqrt(x*x + y*y). To check if this is in the circle, one might test sqrt(x*x + y*y) <= 1.0. However, squaring this test gives an equivalent, but simpler, test: x*x + y*y <= 1.0

Random number operations are common in many languages. In Java, the mathematics library class contains such a mechanism to generate random numbers between 0 and 1, and we will use that library operation.

Code

The resulting program approxPi.java in package mathComputationsfollows the outline very closely. While several parts of this program are familiar, both the conditionals and the looping involve some Java constructs which have not yet been introduced in this course.

Some Syntax

Program approxPi.java provides examples of both conditional (if statements) and for loops. if statements have two forms, analogous to Scheme:

if (condition)
   statement;

if (condition)
   statement1;
else
   statement2;

In each case, the overall condition must be in parentheses and only a single statement can be given. However, as in Scheme, multiple statements can be placed in then or else by grouping them together in brackets { } -- just as a (begin ... ) was used in Scheme.

Also as in Scheme, the condition may be made up of several clauses, combined by such operations as:

	!	not
	&&	and
	||	or

for loops have the following general syntax:

for (initialization ; continue-condition ; update)
   statement;

Here, initialization contains one or more statements (separated by commas) which initialize variables. continue-condition is a Boolean condition. Every time execution gets to the top of the loop, this condition is re-evaluated. If the condition is true, the statement is executed as the body of the loop. The update portion of the code allows variables to be updated from one iteration of the loop to the next.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-java-prob.sol-1.shtml

created April 16, 2000 last revised April 12, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.