java - Javaの宿題（再帰）

Question

これは質問です：

問題I.

Pestaina 文字列を次のように定義します。

1. ab はペステイナ文字列です。
2. cbac は Pestaina 文字列です。
3. S が Pestaina ストリングの場合、SaS も同様です。
4. U と V が Pestaina ストリングの場合、UbV も同様です。

ここで、a、b、c は定数で、S、U、V は変数です。これらの規則では、同じ文字は同じ文字列を表します。したがって、S = ab の場合、ルール 3 により、abaab はペステイナ文字列であることがわかります。ルール 4 では、U と V はおじいちゃんの文字列を表しますが、異なる場合があります。

メソッドを書く

public static boolean isPestaina(String in)

in が Pestaina 文字列の場合は true を返し、そうでない場合は false を返します。

そして、これは私がこれまでに持っているもので、最初のルールでのみ機能しますが、「abaaab」などの機能しない場合もあります。

public class Main {

private static boolean bool = true;
    public static void main(String[] args){

        String pestaina = "abaaab";
        System.out.println(pestaina+" "+pestainaString(pestaina));
    }

    public static boolean pestainaString(String p){

        if(p == null || p.length() == 0 || p.length() == 3) {
            return false;
        }
        if(p.equals("ab")) {
            return true;
        }
        if(p.startsWith("ab")){

            bool = pestainaString(p, 1);
        }else{
            bool = false;
        }
        return bool;
    }

    public static boolean pestainaString(String p, int sign){

        String letter;
        char concat;

        if("".equals(p)){

            return false;
        }


        if(p.length() < 3){

            letter = p;
            concat = ' ';
            p = "";
            pestainaString(p);

        }else if(p.length() == 3 && (!"ab".equals(p.substring(0, 2)) || p.charAt(2) != 'a')){
            letter = p.substring(0, 2);
            concat = p.charAt(2);
            p = "";
            pestainaString(p);
        }else{
            letter = p.substring(0, 2);
            concat = p.charAt(2);
            pestainaString(p.substring(3));
        }

        if(letter.length() == 2 && concat == ' '){
            if(!"ab".equals(letter.trim())){

                bool = false;
                //concat = 'a';
            }

        }else if((!"ab".equals(letter)) || (concat != 'a')){

            bool = false;
        }
        System.out.println(letter +" " + concat);
       return bool;
    }
}

私が間違ったことを教えてください。

Answer 1

あなたは文脈自由言語を記述しています。これは文脈自由文法として記述され、それで解析されます。これらを解析する分野は広​​く研究されており、そこには多くのリソースがあります。

ウィキペディアのページでは、これらを解析するためのいくつかのアルゴリズムについても説明しています。具体的には、アーリーパーサーに興味があると思います。

また、この「言語」は、プッシュダウンオートマトンを使用して解析できると思います（ただし、100％確実ではありません）。

Answer 2

それは楽しかった。

public boolean isPestaina(String p) {
        Set<String> existingPestainas = new HashSet<String>(Arrays.asList(new String[]{"ab", "cbac"}));
        boolean isP  = false;
        int lengthParsed = 0;
        do {
            if (lengthParsed > 0) {
                //just realized there's a touch more to do here for the a/b
                //connecting rules...I'll leave it as an excersize for the readers.
                if (p.substring(lengthParsed).startsWith("a") ||
                    p.substring(lengthParsed).startsWith("b")) {
                    //good connector.
                    lengthParsed++;
                } else {
                    //bad connector;
                    return false;
                }
            }
            for (String existingP : existingPestainas) {
                if (p.substring(lengthParsed).startsWith(existingP)) {
                    isP = true;
                    lengthParsed += existingP.length();
                }
            }
            if (isP) {
                System.err.println("Adding pestaina: " + p.substring(0, lengthParsed));
                existingPestainas.add(p.substring(0, lengthParsed));
            }
        } while (isP && p.length() >= lengthParsed + 1);
        return isP;
    }

Answer 3

間違ったメソッドを呼び出していた問題が見つかりました。

Answer 4

    public static void main(String[] args) {
        // TODO code application logic here
        String text = "cbacacbac";


        System.out.println("Is \""+ text +"\" a Pestaina string? " + isPestaina(text));



    }

    public static boolean isPestaina(String in) {
        if (in.equals("ab")) {
            return true;
        }
        if (in.equals("cbac")) {
            return true;
        }
        if (in.length() > 3) {
            if ((in.startsWith("ab") || in.startsWith("cbac"))
                    && (in.endsWith("ab") || in.endsWith("cbac"))) {
                return true;
            }
        }
        return false;
    }