//------------------------------------------------------------------------ // P5 Q1. // This program can generate a random Blurb, or verify if a given string // is a Blurb. A Blurb is defined as : // // Blurb := Whoozit Whatszit + // Whatszit := q ( z | d ) Whoozit // Whoozit := xy* // In other words Blurb = xy*(q(z|d)xy*)+ // // Wei Tsang Ooi // 2 August 1999 //------------------------------------------------------------------------ import java.io.*; import java.util.*; //----------------------------------------------------------------- // Blurb // // This class provides two static methods, one to check if a string // is a blurb, another returns a random string that is a blurb. //----------------------------------------------------------------- class Blurb { static Random r = new Random(); final static int FALSE = -1; //----------------------------------------------------------------- // prefixedByWhoozit // // This checks if the string s is prefixed by a Whoozit. It returns // FALSE if it is not, otherwise it returns the index of the next // character in the string following the Whoozit. // // Example : isWhoozit("xyyabc") returns 3 because "xyy" is a Whoozit // and "abc" starts from position 3. isWhoozit("cornell") returns // FALSE because it does not start with a Whoozit. //----------------------------------------------------------------- private static int prefixedByWhoozit(String s) { int i = 0; if (s.charAt(i) == 'x') { // Now position i to the end of this whoozit, by skipping // all the y's. i++; while (i < s.length() && s.charAt(i) == 'y') { i++; } return i; } else { // If the string does not start with x, then it is not // prefixed by a Whoozit. So we return FALSE. return FALSE; } } //----------------------------------------------------------------- // isWhatszitList // // This boolean method returns true if the string s is a list of // at least one Whatszit. //----------------------------------------------------------------- private static boolean isWhatszitList(String s) { // First we check if the string is prefixed by one Whatszit. // If this string does not start with a 'qd' or 'qz', then it // cannot be a whatszit. Also, a whatszit must be longer than 3. if ((!s.startsWith("qd") && !s.startsWith("qz")) || s.length() < 3) { return false; } // A Whatszit is a "qd" or "qz" follows by a Whoozit. Check for // Whoozit here. s = s.substring(2); int endOfWhoozit = prefixedByWhoozit(s); // If "qd" or "qz" is not followed by a Whoozit. Bye bye. if (endOfWhoozit == FALSE) return false; // If there is nothing left, then we have exactly one Whatszit. // (terminal case). else if (endOfWhoozit == s.length()) return true; // Otherwise, recursively check for more Whatszit else return isWhatszitList(s.substring(endOfWhoozit)); } //----------------------------------------------------------------- // generateWhoozit // // This function returns a random whoozit. //----------------------------------------------------------------- private static String generateWhoozit() { String s; s = "x"; while (r.nextInt() % 2 == 0) s += "y"; return s; } //----------------------------------------------------------------- // generateWhatszit // // This function returns a random whoozit. //----------------------------------------------------------------- private static String generateWhatszit() { if ( r.nextInt() % 2 == 1) return "qz" + generateWhoozit(); else return "qd" + generateWhoozit(); } //----------------------------------------------------------------- // generateBlurb // // This function returns a random blurb. //----------------------------------------------------------------- static String generateBlurb() { String s = generateWhoozit() + generateWhatszit(); while (r.nextInt() % 2 == 1) s += generateWhatszit(); return s; } //----------------------------------------------------------------- // isBlurb // // A blurb is a Whoozit follows by more than one Whatszit. //----------------------------------------------------------------- static boolean isBlurb(String s) { int endOfWhoozit = prefixedByWhoozit(s); if (endOfWhoozit >= s.length()) return false; else return isWhatszitList(s.substring(endOfWhoozit)); } } public class BlurbMain { static BufferedReader stdin; final static int GENERATE = 1; final static int VERIFY = 2; final static int QUIT = 3; //--------------------------------------------------------- // getInput() // // Return a choice from user. The return value is either // GENERATE, VERIFY or QUIT //--------------------------------------------------------- static int getInput() throws IOException { int input; do { System.out.println("Enter options:"); System.out.println("1) Generate Blurb"); System.out.println("2) Check Blurb"); System.out.println("3) Quit"); System.out.print("> "); input = Integer.parseInt(stdin.readLine()); } while (input < 1 && input > 3); return input; } //--------------------------------------------------------- // generate() // // Keep generating blurb, until user enters 'q'. //--------------------------------------------------------- static void generate() throws IOException { System.out.println("Enter to generate a blurb." + "\n" + "Type q to return to main menu."); String input = stdin.readLine(); while (!input.equalsIgnoreCase("q")) { System.out.println("> " + Blurb.generateBlurb()); input = stdin.readLine(); } } //--------------------------------------------------------- // verify() // // Keep reading blurbs and verify them until user enters 'q'. //--------------------------------------------------------- static void verify() throws IOException { System.out.println("Enter blurb to verify." + "\n" + "Type q to return to main menu."); String input = stdin.readLine(); while (!input.equalsIgnoreCase("q")) { if (Blurb.isBlurb(input)) System.out.println("yes"); else System.out.println("no"); input = stdin.readLine(); } } public static void main(String[] args) throws IOException { stdin = new BufferedReader( new InputStreamReader(System.in)); int input; do { input = getInput(); switch (input) { case GENERATE : generate(); break; case VERIFY : verify(); break; } } while (input != QUIT); System.out.println("bye!"); } }