First you need to test the following complete examples with the data structures defined and given in the text/sample code, pay particular attention to the data structures used in these classes, which are defined in the textbook (not in the JCF!!) and are also provided in the sample code on Canvas: MatchHTML, MatchDelimiters, and Josephus. Make sure that you understand these examples, particularly the algorithms used within. Then you will REIMPLEMENT these 3 classes (examples) with the use of JCFs data structures, such as java.util.Stack, java.util.Queue, java.util.LinkedList and/or others. Create a new folder for your solutionsONLY 3 classes are needed: MatchHTML, MatchDelimiters, and Josephus (because you are using JCFs data structures).

public class Josephus { /** Computes the winner of the Josephus problem using a circular queue. */ public static E Josephus(CircularQueue queue, int k) { if (queue.isEmpty()) return null; while (queue.size() > 1) { for (int i=0; i < k-1; i++) // skip past k-1 elements queue.rotate(); E e = queue.dequeue(); // remove the front element from the collection System.out.println(" " + e + " is out"); } return queue.dequeue(); // the winner }

/** Builds a circular queue from an array of objects. */ public static CircularQueue buildQueue(E a[]) { CircularQueue queue = new LinkedCircularQueue<>(); for (int i=0; i

/** Tester method */ public static void main(String[] args) { String[] a1 = {"Alice", "Bob", "Cindy", "Doug", "Ed", "Fred"}; String[] a2 = {"Gene", "Hope", "Irene", "Jack", "Kim", "Lance"}; String[] a3 = {"Mike", "Roberto"}; System.out.println("First winner is " + Josephus(buildQueue(a1), 3)); System.out.println("Second winner is " + Josephus(buildQueue(a2), 10)); System.out.println("Third winner is " + Josephus(buildQueue(a3), 7)); } } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.Scanner;

/** Simplified test of matching delimiters in a string. */ public class MatchDelimiters {

/** Tests if delimiters in the given expression are properly matched. */ public static boolean isMatched(String expression) { final String opening = "({["; // opening delimiters final String closing = ")}]"; // respective closing delimiters Stack buffer = new LinkedStack<>(); for (char c : expression.toCharArray()) { if (opening.indexOf(c) != -1) // this is a left delimiter buffer.push(c); else if (closing.indexOf(c) != -1) { // this is a right delimiter if (buffer.isEmpty()) // nothing to match with return false; if (closing.indexOf(c) != opening.indexOf(buffer.pop())) return false; // mismatched delimiter } } return buffer.isEmpty(); // were all opening delimiters matched? }

final static String[] valid = { "()(()){([()])}", "( ) ( ( ) ) {( [ ( ) ] ) } ", "(3) (3 + (4 - 5) ) {( [ ( ) ] ) } ", "((()(()){([()])}))", "[(5+x)-(y+z)]" };

final static String[] invalid = { ")(()){([()])}", "({[])}", "(" };

public static void main(String[] args) {

for (String s : valid) if (!isMatched(s)) System.out.println("Error evaluating valid: " + s);

for (String s : invalid) if (isMatched(s)) System.out.println("Error evaluating invalid: " + s);

}

} ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.Scanner;

public class MatchHTML {

/** Tests if every opening tag has a matching closing tag in HTML string. */ public static boolean isHTMLMatched(String html) { Stack buffer = new LinkedStack<>(); int j = html.indexOf('<'); // find first '<' character (if any) while (j != -1) { int k = html.indexOf('>', j+1); // find next '>' character if (k == -1) return false; // invalid tag String tag = html.substring(j+1, k); // strip away < > if (!tag.startsWith("/")) // this is an opening tag buffer.push(tag); else { // this is a closing tag if (buffer.isEmpty()) return false; // no tag to match if (!tag.substring(1).equals(buffer.pop())) return false; // mismatched tag } j = html.indexOf('<', k+1); // find next '<' character (if any) } return buffer.isEmpty(); // were all opening tags matched? }

private final static String example = "" + "" + " " + "

" + " " + "

The Little Boat

" + " " + "" + " " + "

The storm tossed the little" + " " + "boat like a cheap sneaker in an" + " " + "old washing machine. The three" + " " + "drunken fishermen were used to" + " " + "such treatment, of course, but" + " " + "not the tree salesman, who even as" + " " + "a stowaway now felt that he" + " " + "had overpaid for the voyage.

" + " " + "

" + " " + "
1. Will the salesman die?
" + " " + "
2. What color is the boat?
" + " " + "
3. And what about Naomi?
" + " " + "

" + " " + "";

/** * Test the text given as standard input as html. * If command line argument is given, preforms test on example from the book. */ public static void main(String[] args) { if (args.length == 0) { String input = new Scanner(System.in).useDelimiter("\\A").next(); // read entire input at once if (isHTMLMatched(input)) System.out.println("The input file is a matched HTML document."); else System.out.println("The input file is not a matched HTML document."); } else { // use prepared example if (!isHTMLMatched(example)) System.out.println("Error on example"); } }

}

Bonus point question (10 points) In the examples, JCF Strings method, indexOf(char) have used. In your class, implement a method indexOf(String, char) and use this newly implemented method in your solution. 2. (10 points) In the examples, JCF Strings method, indexOf(char, int) have used. In your class, implement a method indexOf(String, char, int) and use this newly implemented method in your solution