java - java作业（递归）

Question

这是问题：

问题一。

我们将 Pestaina 字符串定义如下：

1. ab 是 Pestaina 字符串。
2. cbac 是一个 Pestaina 字符串。
3. 如果 S 是 Pestaina 字符串，那么 SaS 也是。
4. 如果 U 和 V 是 Pestaina 弦，那么 UbV 也是。

这里 a、b、c 是常数，S、U、V 是变量。在这些规则中，相同的字母代表相同的字符串。所以，如果 S = ab，规则 3 告诉我们 abaab 是一个 Pestaina 字符串。在规则 4 中，U 和 V 代表 Grandpa 字符串，但它们可能不同。

写方法

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

我发现我调用了错误的方法的问题。

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

    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;
    }

Answer 4

您正在描述一种Context Free Language，可以将其描述为Context Free Grammer并用它进行解析。解析这些的领域得到了广泛的研究，并且那里有很多资源。

维基百科页面还讨论了一些解析这些的算法，特别是 - 我认为你对早期解析器感兴趣

我也相信可以使用下推自动机来解析这种“语言” （尽管不是 100% 确定）。