Как распаковать данную строку в Java рекурсивно?

Question

это очень легко с помощью итерации, но я должен сделать это с помощью рекурсии. Я пытался вести подсчет того, сколько раз в строке встречается символ, положение и остаток строки и вывод.

public static String uncompress(String compressedText) {

        return uncompress(compressedText, 1, 0, "");

    }

    public static String uncompress(String text, int count, int pos, String output) {

        if (text.equals("")) {

            return "";
        }

        if (Character.isLetter(text.charAt(pos))) {

            output += text.charAt(0);
            pos++;
        }

        else if(Character.isDigit(text.charAt(pos))) {

            count = text.charAt(pos) - '0';
            output += text.charAt(pos + 1);
            count++;
            pos++;

        }

        text = text.substring(pos + 1);

        uncompress(text, count, pos, output);

        return output;
    }

Answer 1

В вашем коде есть несколько ошибок, таких как:

• вы подстраиваетесь, но также передаете позицию, вы должны сделать одну или другую
• ваш базовый случай возвращается"", но вместо этого он должен возвращать накопленную строку 'output'
• , где вы повторяете, что вы игнорируете выходные данные возвращаемого метода и просто возвращаете выходные данные в текущем методе, чтобы ничего не создавалось рекурсией

Ниже приведен код, который использует только рекурсию для анализа строки и создания выходных данных.Я добавил комментарии, чтобы показать, что происходит в коде.Обратите внимание, что, особенно в рекурсии, полезно иметь распечатку текущего состояния, чтобы вы могли видеть, что происходит на каждом этапе, поэтому я также добавил это.

Обратите внимание, что метод getMultiple () находится вСам по себе очень простой пример того, как должна работать рекурсия: вы вызываете один и тот же метод, но либо А) передаете некоторую работу, выполненную в текущем вызове, чтобы его можно было получить в базовом случае, либо Б) берут выходные данные метода идобавьте что-нибудь к нему / измените его перед возвратом измененного вывода.

public class Recursion {

public static void main(String[] args) {
    System.out.println(uncompress("10a2b"));
}

public static String uncompress(String compressedText) {

    return uncompress(compressedText, "", "");

}

public static String getMultiple(char x, int N) {
    if (N == 0) return "";

    return ""+x+getMultiple(x,N-1);
}

public static String uncompress(String text, String count, String output) {
    System.out.println("----");
    System.out.println("TEXT:"+text);
    System.out.println("COUNT:"+count);
    System.out.println("OUTPUT:"+output);


    if (text.equals("")) {
        //base case - no text left to parse

        return output;
    }

    if (Character.isLetter(text.charAt(0))) {
        //letter case - need to take the count we have accrued, parse it into an integer and add to output

        System.out.println(count);// * text.charAt(0);

        output += getMultiple(text.charAt(0),Integer.parseInt(count));

        count = "";
    }

    else if(Character.isDigit(text.charAt(0))) {
        //digit case - need to add to the count but keep as a string because must be parsed later

        count += (""+text.charAt(0));

    }

    //parse the *remainder* of the string, one character at a time, so pass in the substring(1)


      return uncompress(text.substring(1), count, output);
    }
}

Answer 2

Предполагая, что входная строка имеет правильный формат, попробуйте это:

public static String uncompress(String compressedText) {
    if (compressedText.length() == 0)
        return "";
    return uncompress(compressedText, charToInt(compressedText, 0), 0);
}

public static String uncompress(String text, int count, int pos) {
    if (pos == text.length() || (pos == text.length()-2 && count == 0))
        return "";
    else if (count == 0)
        return uncompress(text, charToInt(text, pos+2), pos+2);
    return text.charAt(pos+1) + uncompress(text, count-1, pos);
}

public static int charToInt(String str, int idx) {
    return str.charAt(idx) - '0';
}