Problem With Algorithm Involving Recursion and String Manipulation

[Ashik Uzzaman]

I thought this will be a good forum to have some fun with an algorithm involving recursion and String manipulation. I was writing an Html unescape algorithm in Java today. What I came out with is the one below. There is a problem in the algorithm below that eats up some space or characters for some corner cases. Can you figure out what the problem is?

I wrote the class in a way so that you can compile and run it in command prompt and can see the output right away. You can do some trial and error and figure out the issue in the algorithm below. If you can please, let me know so that I know exactly where I am going wrong.

package com.javaranch.test;

import java.util.*;

/**
* To compiple: javac -d . StringUtils.java
* To run: java com.javaranch.test.StringUtils
*
* @authot ashik
*/
public class StringUtils {

private StringUtils() {}

/**
* the characters to unescape
*/
public static HashMap htmlEntities = new HashMap();
static {
htmlEntities.put("<","<"); htmlEntities.put("<",""); htmlEntities.put(">",">");
htmlEntities.put("'","\'"); htmlEntities.put("'","\'");
htmlEntities.put(""","\""); htmlEntities.put(""","\"");
htmlEntities.put("&","&"); htmlEntities.put("&","&");
htmlEntities.put(" "," "); htmlEntities.put(" "," ");
}

public static final String unescapeHTML(String source, int start){
int i,j;

i = source.indexOf("&", start);
if (i > -1) {
j = source.indexOf(";" ,i);
if (j > i) {
String entityToLookFor = source.substring(i , j + 1);
System.out.println("source = " + source + ", entityToLookFor = " + entityToLookFor + ", i = " + i + " and j = " + j);
if(entityToLookFor.lastIndexOf("&") > entityToLookFor.indexOf("&")) {
i = entityToLookFor.lastIndexOf("&") + 1;
System.out.println("Before source = " + source + ", entityToLookFor = " + entityToLookFor + ", i = " + i + " and j = " + j);
entityToLookFor = entityToLookFor.substring(entityToLookFor.lastIndexOf("&"));
System.out.println("After source = " + source + ", entityToLookFor = " + entityToLookFor + ", i = " + i + " and j = " + j);
}
String value = (String)htmlEntities.get(entityToLookFor);
if (value != null) {
source = new StringBuffer().append(source.substring(0 , i)).append(value).append(source.substring(j + 1)).toString();
return unescapeHTML(source, i + 1); // recursive call
}
}
}
return source;
}

public static void main(String args[]) throws Exception {
// to see accented character to the console
java.io.PrintStream ps = new java.io.PrintStream(System.out, true, "Cp850");

ps.println("Finally: Ashik's Quote <Test Ok = " + unescapeHTML("Ashik's Quote ><Test Ok", 0));
ps.println("-----------");
ps.println("Finally: M& M > 5 = " + unescapeHTML("M& M > 5", 0));
ps.println("-----------");
ps.println("Finally: M & M > 5 = " + unescapeHTML("M & M > 5", 0));
ps.println("-----------");
ps.println("Finally: M &M > 5 = " + unescapeHTML("M &M > 5", 0));
ps.println("-----------");
ps.println("Finally: M& M> 5 = " + unescapeHTML("M& M> 5", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Apos\'trophie & "quote" is <present>", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Please check for empty space in Order Review tab.", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Also check for Billing Information & Subscription Information & Order Review tabs.", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("It's difficult to check today's capitalization strategy for all tabs.", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Remember that 12 is > 9 is > 4", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Similarly 8 is < 10 is < 15", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Shakespeare said,"To be or not to be that is the question."", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Think & think about New York's <best pizza> as the \"ultimate\" pizza!", 0));
ps.println("-----------");
ps.println("Also: \n-->" + unescapeHTML("Apos'trophie & "quote" is <present>", 0));
ps.println("-----------");
}

}

[M K Rayapudi]

Few typos/mistakes are corrected, now your code looks as follows:

package com.javaranch.test;  
import java.util.*;
/**
 * To compiple: javac -d . StringUtils.java To run: java
 * com.javaranch.test.StringUtils
 *
 * @authot ashik 
 */
public class StringUtils {  
  
private StringUtils() {}  
  
/**
 * the characters to unescape
 */  
public static HashMap htmlEntities = new HashMap();  
static {  
htmlEntities.put("<","<"); htmlEntities.put("<",""); htmlEntities.put(">",">");  
htmlEntities.put("\'","\'"); htmlEntities.put("'","\'");  
htmlEntities.put("\"","\""); htmlEntities.put("\"","\"");  
htmlEntities.put("&","&"); htmlEntities.put("&","&");  
htmlEntities.put(" "," "); htmlEntities.put(" "," ");  
}  
  
public static final String unescapeHTML(String source, int start){  
int i,j;  
  
i = source.indexOf("&", start);  
if (i > -1) {  
j = source.indexOf(";" ,i);  
if (j > i) {  
String entityToLookFor = source.substring(i , j + 1);  
System.out.println("source = " + source + ", entityToLookFor = " + entityToLookFor + ", i = " + i + " and j = " + j);  
if(entityToLookFor.lastIndexOf("&") > entityToLookFor.indexOf("&")) {  
i = entityToLookFor.lastIndexOf("&") + 1;  
System.out.println("Before source = " + source + ", entityToLookFor = " + entityToLookFor + ", i = " + i + " and j = " + j);  
entityToLookFor = entityToLookFor.substring(entityToLookFor.lastIndexOf("&"));  
System.out.println("After source = " + source + ", entityToLookFor = " + entityToLookFor + ", i = " + i + " and j = " + j);  
}  
String value = (String)htmlEntities.get(entityToLookFor);  
if (value != null) {  
source = new StringBuffer().append(source.substring(0 , i)).append(value).append(source.substring(j + 1)).toString();  
return unescapeHTML(source, i + 1); // recursive call
}  
}  
}  
return source;  
}  
  
public static void main(String args[]) throws Exception {  
// to see accented character to the console
java.io.PrintStream ps = new java.io.PrintStream(System.out, true, "Cp850");  
  
ps.println("Finally: Ashik's Quote <Test Ok = " + unescapeHTML("Ashik's Quote ><Test Ok", 0));  
ps.println("-----------");  
ps.println("Finally: M& M > 5 = " + unescapeHTML("M& M > 5", 0));  
ps.println("-----------");  
ps.println("Finally: M & M > 5 = " + unescapeHTML("M & M > 5", 0));  
ps.println("-----------");  
ps.println("Finally: M &M > 5 = " + unescapeHTML("M &M > 5", 0));  
ps.println("-----------");  
ps.println("Finally: M& M> 5 = " + unescapeHTML("M& M> 5", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Apos\'trophie & \"quote\" is <present>", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Please check for empty space in Order Review tab.", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Also check for Billing Information & Subscription Information & Order Review tabs.", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("It's difficult to check today's capitalization strategy for all tabs.", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Remember that 12 is > 9 is > 4", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Similarly 8 is < 10 is < 15", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Shakespeare said,\"To be or not to be that is the question.\"", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Think & think about New York's <best pizza> as the \"ultimate\" pizza!", 0));  
ps.println("-----------");  
ps.println("Also: \n-->" + unescapeHTML("Apos'trophie & \"quote\" is <present>", 0));  
ps.println("-----------");  
}  
  
}    

and the output is:

Finally: Ashik's Quote <Test Ok = Ashik's Quote ><Test Ok
-----------
Finally: M& M > 5 = M& M > 5
-----------
Finally: M & M > 5 = M & M > 5
-----------
Finally: M &M > 5 = M &M > 5
-----------
Finally: M& M> 5 = M& M> 5
-----------
Also:
-->Apos'trophie & "quote" is <present>
-----------
Also:
-->Please check for empty space in Order Review tab.
-----------
Also:
-->Also check for Billing Information & Subscription Information & Order Review tabs.
-----------
Also:
-->It's difficult to check today's capitalization strategy for all tabs.
-----------
Also:
-->Remember that 12 is > 9 is > 4
-----------
Also:
-->Similarly 8 is < 10 is < 15
-----------
Also:
-->Shakespeare said,"To be or not to be that is the question."
-----------
Also:
-->Think & think about New York's <best pizza> as the "ultimate" pizza!
-----------
Also:
-->Apos'trophie & "quote" is <present>
-----------

I didn't get you what you are expecting the output to be?

[Ashik Uzzaman]

I see the problem here. JavaRanch is converting or escaping the characters that I wanted to escape through coding. I thout the

 tag will preserve my content inside it, but it's not . For example - 

[code]htmlEntities.put("<","<"); htmlEntities.put("<","")

I did not want to add the same character twice. Instead one of these two will be & # 6 0 ; and the other will be & l t ; (keeping space for each character but there will be so space and those should be treated as one string). Same for all the others.

I tried to attach the source code but the forum is not allowing .java, .htm, .txt, .abc extension files. So I don't know how I can attach the file itself.

By the way, I believe the problem in logic is around these 2 lines.

   i = entityToLookFor.lastIndexOf("&") + 1;
   entityToLookFor = entityToLookFor.substring(entityToLookFor.lastIndexOf("&"));

[Ashik Uzzaman]

I am attaching 2 GIF images one by one that has the source code. I am not sure if it will be enough for understanding but it will show you the different between the code posted and what I actually wrote.

[Ashik Uzzaman]

And here is the second page where the main() is written. Please see if this helps to describe the problem.

[Ulf Dittmer]

It would be much better if you posted properly indented code using CODE tags instead of posting screenshots - much more likely that people will actually read it.