Java program (beginner) help?!

Hi,

I have to write a program that decompresses a string in RLE recursively WITHOUT any loops. I've just learned recursion...and I think I understand it mostly (calling a method within itself). But I can't seem to wrap my head around this problem!

Ex:
Given a String str = 5w2Kr3qO
Output: wwwwwKKrqqqO

(so you output the letter according to the number/count which precedes it; if there is no number preceding the letter, then the letter is printed once)


I'm really confused about how to approach this problem, any hints would be appreciated.



This was my initial approach, but it does not work:

Code Java:

---

public static String decompress (String str){
 
if(str.length()==1)
return str;
 
String first="";
String rest="";
char c = str.charAt(0);
 
if(Character.isLetter(c) == true){
first = str.substring(0,1);
rest = str.substring(1);
return first + decompress(rest);
 
}else{
first = str.substring(0,2);
rest = str.substring(2);
int x = str.charAt(0);
char y = str.charAt(1);
return repeat(x, y) + decompress(rest); // repeat is a method which will repeat y for x times
}
 
 
}

---

What are the results of using that decompress method? Does it throw an exception or does it give an incorrect String?

It appears that when the decompress method receives a 2-character input String made up of number and character (like "2d"), the "rest" String will end up becoming an empty String. Then that empty String will be placed in the recursive call of the decompress method. It does not appear that your method handles empty Strings. Perhaps this change will work:

Code java:

---

public static String decompress (String str){
 
if(str == "" || str.length()==1)
return str;
.....
}

---

I hope that helps!

Quote:

---

Originally Posted by Gigggas

What are the results of using that decompress method? Does it throw an exception or does it give an incorrect String?

It appears that when the decompress method receives a 2-character input String made up of number and character (like "2d"), the "rest" String will end up becoming an empty String. Then that empty String will be placed in the recursive call of the decompress method. It does not appear that your method handles empty Strings. Perhaps this change will work:

Code java:

---

public static String decompress (String str){
 
if(str == "" || str.length()==1)
return str;
.....
}

---

I hope that helps!

---

Thank you for your suggestion. I understand now that I didn't account for null strings. I'm still getting an error though, and I'm not sure why or how to fix it. I've tried tracing my code with paper, but I can't seem to figure out what's wrong. The error says:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String Index out of range: 0

at java.lang.String.charAt(String.java:695)
at rle.decompress(rle.java:20)
at rle.decompress(rle.java:31)
at test.main(test.java:8)

(class with the decompress method)
line 20: char c = str.charAt(0);
line 31: return repeat(x, y) + decompress(rest);

(class that calls/tests decompress method)
line 8: String answer = rle.decompress(x);

Quote:

---

Originally Posted by rk2010

Thank you for your suggestion. I understand now that I didn't account for null strings. I'm still getting an error though, and I'm not sure why or how to fix it. I've tried tracing my code with paper, but I can't seem to figure out what's wrong. The error says:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String Index out of range: 0

at java.lang.String.charAt(String.java:695)
at rle.decompress(rle.java:20)
at rle.decompress(rle.java:31)
at test.main(test.java:8)

(class with the decompress method)
line 20: char c = str.charAt(0);
line 31: return repeat(x, y) + decompress(rest);

(class that calls/tests decompress method)
line 8: String answer = rle.decompress(x);

---

Can you post the repeat(x, y) method?

Code java:

---

if(str == "")

---

You shouldn't use the == operator to compare Strings. You should use the String's equals() method.

Code java:

---

if(str.equals(""))

---

Sure! Here is the repeat method that I'm using:

Code Java:

---

public static String repeat(int i, char c){
     String tst = "";
 
     for(int j = 0; j < i; j++){
     tst = tst+c;
     }
 
     return tst;
}

---

And thanks! I can't believe I missed that. I always forget to use .equals for strings. I fixed the base case in my decompress method to (str.equals("") || str.length()==1). Now I don't have any errors!!! But the problem is that my program is not outputting the correct amount of letters.

For instance,
If I input: 2d
I get: dddddddddddddddddddddddddddddddddddddddddddddddddd

(I get 51 d's)
But I should just get: dd

I think the problem is in your the parameters you pass when you call the repeat(int i, char c) method. To be more specific:

Code java:

---

int x = str.charAt(0);

---

In the abode code x has the value of the char at index 0. You can put a print statement after that piece of code to see the value of x. If i were you, i would take the substring that contains the int and then use the Integer's parseInt() method to take the int from the String input.
Hope i was clear.

Thank you so much andreas!!!!
I used: int x = Integer.parseInt(str.substring(0,1));
And now my program works perfectly!

Quote:

---

Originally Posted by rk2010

Thank you so much andreas!!!!
I used: int x = Integer.parseInt(str.substring(0,1));
And now my program works perfectly!

---

You are welcome.
Glad you got it work.