Problem Class Questions for

COMP1007 (Programming Principles) Week 4, 2005

1. Evaluate the following Java statements by hand to explain either the value each variable is initialised to or why the statement is invalid:

a) int a = 10 - 3 * 6 + 7 / 2;

b) int b = 2 * 3 * 4 / 5 * 6;

c) int c = 3 / (6 / 9);

d) int d = 4/5/6;

e) int e = 12345678 * 78910112 * 4567895 * 10;

f) double f = 2 + 3;

g) float g = 2 + 3;

h) String h = "Hello" + "World"; 

i) String i = "Hello" - "o";

j) String j = 2 + "3";

k) char k = 'a' + 3;

l) double l = 2.345 + 6 * 4.55 / 3.5 - 5.4;

m) int[] m = new int[1];

n) int[][]n = new int[20][];

o) String[] o = new String[5][5];

p) boolean[] p = new int[5];

q) long[][][] q = new long[4][][4];

r) int r = 3 + 5.1 * 10;

After the problem class, put these declarations in to a program and try to compile/run them.

2. A String is a sequence of characters, and a String variable in Java can be declared like this:

String message = "Hello World"; 

The individual characters can be accessed with the method charAt(), for example:

char c = message.charAt(0); // c is initialised to 'H', as counting starts at 0
char d = message.charAt(5); // d is initialised to the space character

The number of characters in a String can be determined using the length() method:

int n = message.length(); // n is initialised to 11

An algorithm to find the position of a character in a String can be expressed as follows:

String text = "Some text";
char c = 'x'; 
int position = -1; 
for (int n = 0 ; n < text.length() ; n++) 
{ 
  if (text.charAt(n) == c) // See if the character at position n has the same value as c 
  { 
    position = n;
  } 
} // After the loop position should have the value 7, counting from 0. 

Note that the algorithm is expressed in Java code but the intention is to capture the detail of the algorithm not to worry about precise Java syntax. You should be able to follow the algorithm in your head or by making notes to determine what it does.

The following questions don't require a computer to answer them but you might want to turn your answers into working programs after the problem class to confirm they work correctly. Your answers will require additional variables, loops and if statements. You may want to break your algorithms into a collection of methods (functions), each solving a sub-part of the problem.

a) Modify the example algorithm above so that it finds the position of the first occurrence of a character in a String. For example, initialising c to 't' will leave position with the value 5. If the character is not in the String, position is left with the value -1.

b) Modify the example algorithm again so that it finds the position of the nth occurrence of a character. For example:

String text = "Some text"; 
char c = 't'; 
int occurrence = 2; 

Will leave position with the value 9, the position of the 2nd occurrence of 't'.

c) Write an algorithm to find the position of a Substring within a String. For example, starting with:

String text = "Some text";
String substring = "me";
int startposition = -1;
int endposition = -1; 

Will leave startposition with the value 2, which is the position where the substring "me" begins in "Some text", and endposition with the value 3, which is the position where "me" ends. If the substring is not present both startposition and endposition should be left with the value -1.

3. A wildcard matches one or more characters in a String. The wildcard '?' will match a single character, while '*' will match multiple characters.

Searching for the substring pattern "a?b" will find any substring that starts with the character 'a', followed by any character, followed by 'b'. For example:

String text = "Some text";
String substring = "o?e";
int startposition = -1;
int endposition = -1; 

Will leave startposition with the value 1, and enposition with the value 3, as the substring "ome" will match.

Searching for the substring pattern "a*b" will find any substring that starts with the character 'a', followed by a sequence of characters of any length (including zero), followed by 'b'. For example:

String text = "Some text";
String substring = "m*x";
int startposition = -1;
int endposition = -1 

Will leave startposition with the value 2, and endposition with the value 7 as the substring "me tex" will match. A search for the substring pattern "S*o" will leave startposition with the value 0, and endposition with the value 1, as the substring "So" will match.

a) Develop an algorithm to search for substrings using the '?' wildcard character.

b) Extend your algorithm to work with the '*' wildcard character as well. Note - it may be easier to solve simpler versions of the problem first and work your way up to the full version step-by-step.

Substring patterns can use multiple wildcards, for example: "ab?c*d". Make sure your answer to b can deal with any pattern.

4. The wildcard [ ] is introduced. This allows a selection from a set of characters. For example "[ac]" would match either 'a' or 'c', and "[a-d] specifies the range from 'a' to 'd' inclusive and would match 'a' or 'b' or 'c' or 'd'.

a) Develop an algorithm to search for substrings using the [ ] wildcard only.

b) Now combine your answer from a) with your algorithm from 4b). Make sure your algorithm will work with combinations of wildcards, for example: "th?[mn]" would match "than", "then", "them", "thin". "file*[0-9]" would match "fileName0", "fileName1" …, "fileName9".

Note that the system of wildcards explored in these questions is a standard used by operating systems such as Unix and also within programming languages. *, ? and [ ] are a subset of something called "Regular Expressions".

The Unix command line is a good example of where wildcards are used, typically to match file and directory names. For example, the command ls file*[0-9] would list any files in the current directory whose names match the pattern. Experiment with the ls command to get used to using wildcards.