I trying to figure out the best way to find the number of valid HTML tags in a string.
The assumption is that the tag is valid only if it has an opening and closing tag
this is an example of a test case
INPUT
"html": "<html><head></head><body><div><div></div></div>"
Output
"validTags":3
Do not do it yourself. There is no need to reinvent the wheel. There is a plethora of libraries for parsing HTML. Use the proper tool for the proper job.
Concentrate your efforts on the rest of your project. Sure, you could implement your own function that parses a string, looks for < and >, and acts appropriately. But HTML might be slightly more complex than you imagine, or you might end up needing more HTML parsing than just counting tags.
Maybe in the future you'llwant to count <br/> and <br /> as well. Or you'll want to find the depth of the HTML tree.
Maybe your homemade code doesn't account for all possible combinations of escaping characters, nested tags, etc. How many correct tags are there in the string:
<a><b><c><d e><f g="<h></h>"><i j="<k>" l="</k>"></i></f></e d></b></c></ a >
In a comment, user dbl linked to a similar question with links to libraries: How to validate HTML from java ?
Here is a proposed algorithm in pseudocode, as a recursive function:
function count_tags(s):
tag, remainder = find_next_tag(s)
found, inside, after = find_closing_tag(tag, remainder)
if (found)
return 1 + count_tags(inside) + count_tags(after)
else
return count_tags(inside)
Examples
hello <a>world<c></c></a><b></b>, we will get:tag = "<a>"
remainder = "world<c></c></a><b></b>"
found = true
inside = "world<c></c>"
after = "<b></b>"
return 1 + count_tags("world<c></c>") + count_tags("<b></b>")
<html><head></head>:tag = "<html>"
remainder = "<head></head>"
found = false
inside = "<head></head>"
after = ""
return count_tags("<head></head>")
<a><b></a></b>:tag = "<a>"
remainder = "<b></a></b>"
found = true
inside = "<b>"
after = "</b>"
return 1 + count_tags("<b>") + count_tags("</b>")
I wrote a function that would do exactly this.
static int checkValidTags(String html,String[] openTags, String[] closeTags) {
//openTags and closeTags must have the same length;
//This function keeps track of all opening tags.
//and removes the opening and closing tags if the tag is closed correctly
//It can even detect when there are labels added to the tags.
HashMap<Character,Integer> open = new HashMap<>();
HashMap<Character,Integer> close = new HashMap<>();
//Use a start character, this is 1 because 0 would be a string terminator.
int startChar = 1;
for(int i = 0; i < openTags.length; i++) {
open.put((char)startChar, i);
close.put((char)(startChar+1), i);
html = html.replaceAll(openTags[i],""+ (char)startChar);
html = html.replaceAll(closeTags[i],""+(char)(startChar+1));
startChar+=2;
}
List<List<Integer>> startIndexes = new ArrayList<>();
int validLabels = 0;
for(int i = 0; i < openTags.length; i++) {
startIndexes.add(new ArrayList<>());
}
for(int i = 0; i < html.length(); i++) {
char c = html.charAt(i);
if(open.get(c)!=null) {
startIndexes.get(open.get(c)).add(0,i);
}
if(close.get(c)!=null&&!startIndexes.get(close.get(c)).isEmpty()) {
String closed = html.substring(startIndexes.get(close.get(c)).get(0),i);
for(int k = 0; k < startIndexes.size(); k++) {
if(!startIndexes.get(k).isEmpty()) {
int p = startIndexes.get(k).get(0);
if(p > startIndexes.get(close.get(c)).get(0)) {
startIndexes.get(k).remove(0);
}
}
}
startIndexes.get(close.get(c)).remove(0);
html.replace(closed, "");
validLabels++;
}
}
return validLabels;
}
And to use it in your example you would do like this:
String html = "<html><head></head><body><div><div></div></div>";
int validTags = checkValidTags(html,new String[] {
//Add here all the tags you are looking for.
//Remove the trailing '>' so it can detect extra tags appended to it
"<html","<head","<body","<div"
}, new String[]{
"</html>","</head>","</body>","</div>"
});
System.out.println(validTags);
Output:
3