COP 3337
Section U05
Spring 2016



                       A RECURSIVE PROGRAM
                       ===================


Problem  I. We define the Shaw strings as follows:

      1. abb is a Shaw string.

      2. bca is a Shaw string.

      3. If S is a Shaw string, so is SaS.

      4. If U and V are Shaw strings, so is UbV.

Here a, b, c are constants and S,U,V are variables. In these rules,
the same letter represents the same string. So, if S = abb,
rule 3 tells us that abbaabb is a Shaw string.
In rule 4, U and V represent Shaw strings, but they may be different.

Write the method

public static boolean isShaw(String in)
     that returns true if in is a Shaw string and false otherwise.

Solution:

   // check if in is a Shaw string
    public static boolean isShaw(String in)
    {
        // check if in is one of the base strings
        if (in.equals("abb") || in.equals("bca"))
            return true;
        // reject the strings of even length and the ones
        // of length <= 6
        int len = in.length();
        if (len % 4 != 3 || len <= 6)
            return false;

        // check rule 3
        int mid = len / 2;
        if (in.charAt(mid) == 'a')
        {
            // get s1 and s2
            String s1 = in.substring(0,mid);
            String s2 = in.substring(mid+1);
            if (s1.equals(s2) && isShaw(s1))
                return true;
        }

        // check rule 4
        for (int i = 3; i < len-3; i = i + 4 )
        {
            // the separator is at i. check if it is b
            if (in.charAt(i) == 'b')
            {
                // get u and v
                String u = in.substring(0,i);
                String v = in.substring(i+1);
                if (isShaw(u) && isShaw(v))
                    return true;
            }
        }

        // all 4 cases failed
        return false;

    }