7.8. Processing Each Character in a StringMany string-processing applications require you to process every character in a string. For example, to encrypt the string "hello" into "jgnnq", we have to go through every letter of the string and change each character to its substitute. Algorithms of these types usually involve a counting loop bounded by the length of the string. Recall that the length() method determines the number of characters in a String and that strings are zero indexed. This means that the first character is at index 0, and the last character is at index length()-1. For example, to print each character in a string on a separate line, we would step through the string from its first to its last character and print each character: // Precondition: str is not null // Postcondition: the letters in str will have been printed public void printLetters(String str) { for (int k = 0; k < str.length(); k++)// For each char System.out.println(str.charAt(k)); // Print it }
Counting-loop algorithm Our loop bound is k < str.length(), since the index of the last character of any String is length()-1. Note the use of str.charAt(k) to retrieve the kth character in str on each iteration of the loop.
Counting bound As you will have observed, pre- and postconditions are used in the method's comment block. The precondition states that str has been properly initializedthat is, it is not null. The postcondition merely states the expected behavior of the method. 7.8.1. Off-by-One ErrorA frequent error in coding counter-controlled loops is known as the off-by-one error. Such errors can occur in many different ways. For example, if we had coded the loop boundary condition as k <= str.length(), this would cause an off-by-one error because the last character in str is at location length()-1. This would lead to a Java IndexOutOfBoundsException, which would be reported as soon as the program executed this statement.
Off-by-one error The only way to avoid off-by-one errors is to check your loop bounds whenever you code a loop. Always make sure you have the loop counter's initial and final values right. Debugging Tip: Off-by-One Errors
7.8.2. Example: Counting CharactersAs another example of an algorithm that processes every character in a string, consider the problem of computing the frequency of the letters in a given document. Certain text-analysis programs, such as programs that analyze encrypted data and spam filters, perform this type of function. The countChar() method will count the number of occurrences of any particular character in a String (Fig. 7.11). This method takes two parameters: a String parameter that stores the string being searched, and a char parameter that stores the character being counted. Figure 7.11. A method to count the occurrences of a particular character in a string.
Method design Begin by initializing the local variable, counter, to 0. As in the preceding example, the for loop here will iterate through each character of the Stringfrom 0 to length()-1. On each iteration a check is made to see if the character in the kth position (str.charAt(k)) is the character being counted. If so, counter is incremented. The method ends by returning counter, which, when the method completes, will store an integer representing the number of ch's in str.
Algorithm design 7.8.3. Example: Reversing a StringAnother interesting method that processes every character in a string is the reverse() method. This method reverses the letters in a string. For example, the reverse of "java" is "avaj".
Algorithm design The algorithm for the reverse() method should use a simple counting loop to reverse the letters in its String parameter. In this case, however, we can process the string from right to left, beginning at its last character and ending with its first character. That way we can just append each character, left to right, in the result string: /** * Pre: s is any non null string * Post: s is returned in reverse order */ public String reverse(String s) { StringBuffer result = new StringBuffer(); for (int k = s.length()-1; k >= 0; k--) { result.append(s.charAt(k)); } // for return result.toString(); } // reverse() As in the other string-manipulation algorithmsfor example, keywordSearch()we should use a StringBuffer to store the method's result. Thus we declare the result StringBuffer at the beginning of the method and convert it back into a String at the end of the method. Java Programming Tip: Changing Each Character in a String
7.8.4. Example: Capitalizing the First LetterAnother string-manipulation method is the capitalize() method, which returns a String whose initial letter is capitalized but whose other letters are lowercasefor example, "Hello". We use the static toUpperCase() and toLowerCase() methods from the Character class to convert individual letters. We could also have used the methods of the same name that we wrote in Section 5.7. The algorithm converts the first letter to uppercase and then loops through the remaining letters converting each to lowercase: /* * Pre: s is any non null string * Post: s is returned with only its first letter capitalized */ public String capitalize(String s) { if (s.length() == 0) // Special case: empty string return s; StringBuffer result = new StringBuffer(); result.append(Character.toUpperCase(s.charAt(0)));// Convert the first letter for (int k = 1; k < s.length(); k++) { // And the rest result.append(Character.toLowerCase(s.charAt(k))); } // for return result.toString(); } // capitalize()
Algorithm design Self-Study Exercises
7.8.5. Miscellaneous String MethodsIn addition to the several String class methods we have discussedvalueOf(), equals(), indexOf(), lastIndexOf(), charAt(), substring()Table 7.2 shows some of the other useful methods in the String class. Because of the read-only nature of Strings, methods such as toUpperCase(), toLowerCase(), and trim() do not change their strings. Instead they produce new strings. If you want to use one of these methods to convert a string, you must reassign its result back to the original string: String s = new String("hello world"); s = s.toUpperCase(); // s now equals "HELLO WORLD"
|