HOW TO CHECK IF DOM ELEMENTS ARE CORRECTLY NESTED

user_9752510 0
Viewed 15770

i need help with this coding challenge.

Have the function HTMLElements(str) read the str parameter being passed which will be a string of HTML DOM elements and plain text. The elements that will be used are: b, i, em, div, p. For example: if str is "<div><b><p>hello world</p></b></div>" then this string of DOM elements is nested correctly so your program should return the string true.

If a string is not nested correctly, return the first element encountered where, if changed into a different element, would result in a properly formatted string. If the string is not formatted properly, then it will only be one element that needs to be changed. For example: if str is "<div><i>hello</i>world</b>" then your program should return the string div because if the first element were changed into a <b>, the string would be properly formatted.

example:

Input: "<div><div><b><b/></div><p/>"
output: <div>

Input: "<div>abc</div><p><em><i>test test test</b></em></p>"
output: i

Here is how far I've gotten:

function HTMLElements(str) { 

 let openingTag = str.match(/<\w+>/g)
 let closingTag = str.match(/(<\/\w+>)/g)
 let strObj = {
  '<div>': '</div>',
  '<p>': '</p>',
  '<i>': '</i>',
  '<p>': '</p>',
  '<em>': '</em>',  
  '<b>': '</b>',
  }

  let unclosedElem = []

  for(let i=0; i<openingTag.length; i++){
     console.log(closingTag)
    if(closingTag.indexOf(strObj[openingTag[i]]) ===-1){
      unclosedElem.push(closingTag.splice(closingTag.indexOf(strObj[openingTag[i]]),1))
    }
  }
  console.log(unclosedElem)
  if(unclosedElem.length === 0) return true;
  return unclosedElem[0]
} 

// keep this function call here 
HTMLElements("<div><div><b><b/></div></p>")

now i understand this is far from solving the challenge but i guess it's a start for me. I will eventually solve this but your inputs are appreciated

html javascript
6 Answers

There are a couple of issues.

First, you are doing closingTag.indexOf(...) === -1. If it's equal to -1, it means that this closing tag was not found at all. But the requirement is to "detect a problem" even if the closing tag is here, but in the wrong order (not nested correctly).

So, a first fix you could do is:

closingTag.indexOf(...) !== closingTag.length - i

This would count backward from the end of the closing tags array. Because the first opening tag corresponds to the last closing tag.

But then, we have a problem. indexOf will return the first occurrence of a tag. But what if we have multiple div tags nested inside of each other? It would not know which one you're referring to.

My suggestion, instead of using indexOf, would be to go from left to right in the opening tags array, while going from right to left in the closing tags array. An easy way to do it is to .reverse() the second array so that you can go in the same direction with both:

function HTMLElements(str) {
  let openingTags = str.match(/<\w+>/g)
  let closingTags = str.match(/(<\/\w+>)/g).reverse();
  let strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };
  
  // There might not be the same number of opening and closing tags
  const max = Math.max(openingTags.length, closingTags.length);
  
  for (let i = 0; i < max; i++) {
    if (strObj[openingTags[i]] !== closingTags[i]) {
      return (openingTags[i] || closingTags[i]).replace(/<|>/g, '');
    }
  }

  return true;
}

function demo(str) {
  const res = HTMLElements(str);
  console.log(str, '\t--> ', res);
}

demo("<div><div><b><b/></div></p>"); // "div" (closing a `div` with a `p`)
demo("<p><div><b><b/></div></p>");   // "b" (because `<b/>` is invalid)
demo("<p><div></p></div>");          // "p" (wrong order)
demo("<p><div><b></b>");             // "p" (not closed at all)
demo("<p><div></b></div></p>");      // "/b" (not opened)
demo("<p><div><b></b></div></p>");   // true

user_19137290

I have worked an alternative solution, based on the one posted by blex. As a note, this method does not take into account if the tag is malformed, so it might be necessary to watch out for that.

function HTMLElements(str) {
    let openingTags = str.match(/<\w+>/g)
    let closingTags = str.match(/(<\/\w+>)/g);
    let sin_par = []

    for (const ciclo_1 in openingTags) {
        tiene_par = false
        for (ciclo_2 in closingTags) {
            //console.log("##: " + openingTags[ciclo_1] + " : " + closingTags[ciclo_2])
            if (openingTags[ciclo_1] === closingTags[ciclo_2].replace("/", "")) {
                closingTags.splice(ciclo_2, 1)
                tiene_par = true
            }
        }
        
        if (tiene_par == false) {
            //console.log("etiqueta sin par: " + openingTags[ciclo_1].replace(/<|>/g, ''))
            sin_par.push(openingTags[ciclo_1].replace(/<|>/g, ''))
        } 
    }
    longitud = sin_par.length
    //console.log("RESULTADO: " + sin_par)
    return longitud>0 ? sin_par[0] : true;

}


console.log(HTMLElements("<div><div>abc</div><p>hola</p></div>"));
console.log(HTMLElements("<div></div><b></b>"));
console.log(HTMLElements("<div><div><b></b></div>/</p>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));

user_88591040

Further work on blex's solution to account for case strings such as <div>abc</div><p><em><i>test test test</b></em></p> where the div tag was opened and closed right away and not having any other tags nested in it.

function HTMLElements(str) {
  const openingTags = str.match(/<\w+>/g)
  const closingTags = str.match(/(<\/\w+>)/g);
  
  const strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };
  
  // there might not be the same number of opening and closing tags
  const max = Math.max(openingTags.length, closingTags.length);
  
  for (let i = 0; i < max; i++) {
    if (strObj[openingTags[i]] !== closingTags[closingTags.length - 1] && strObj[openingTags[i]] !== closingTags[0]) {
      return (openingTags[i]).replace(/<|>/g, '');
    }
      closingTags.splice(closingTags.indexOf(strObj[openingTags[i]]),1);
  }

  return "true";
}

console.log(HTMLElements("<div><b><p>hello world</p></b></div>"));
console.log(HTMLElements("<div><i>hello</i>world</b>"));
console.log(HTMLElements("<div><div><b><b/></div><p/>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));
console.log(HTMLElements("<div><p></p><em><div></div></em></div>"));

But when I think more deeply about the problem and take into account "If a string is not nested correctly, return the first element encountered where, if changed into a different element, would result in a properly formatted string. If the string is not formatted properly, then it will only be one element that needs to be changed", this condition sure helps, knowing that it can only be one element not nested correctly That said, I think a better solution and approach would be:

function HTMLElements(str) {
  const openingTags = str.match(/<\w+>/g)
  const closingTags = str.match(/(<\/\w+>)/g);
  
  const strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };

  for(let i = 0; i < openingTags.length; i++) {
    const openingTag = openingTags[i];
    const closingTag = strObj[openingTag];
    if (closingTag) {
      const closingTagIndex = closingTags.indexOf(closingTag);
      if (closingTagIndex > -1) {
        closingTags.splice(closingTagIndex, 1);
      }
      else return openingTags[i].replace(/<|>/g, '');
    }
  }
  return "true";
}

console.log(HTMLElements("<div><b><p>hello world</p></b></div>"));
console.log(HTMLElements("<div><i>hello</i>world</b>"));
console.log(HTMLElements("<div><div><b><b/></div><p/>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));
console.log(HTMLElements("<div><p></p><em><div></div></em></div>"));

Another approach would be to make a frequency count of the tags using dictionaries and do a comparison for the ones that don't add up:

function HTMLElements(str) {
  const openingTags = str.match(/<\w+>/g)
  const closingTags = str.match(/(<\/\w+>)/g);
  
  const strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };
  
  const expectedClosingTagsDict = {};
  openingTags.forEach(tag => {
    const validClosingTag = strObj[tag];
    if(validClosingTag) {
      expectedClosingTagsDict[validClosingTag] ? expectedClosingTagsDict[validClosingTag]++ : expectedClosingTagsDict[validClosingTag] = 1;
    }
  });

  const actualClosingTagsDict = {};
  closingTags.forEach(tag => {
    actualClosingTagsDict[tag] ? actualClosingTagsDict[tag]++ : actualClosingTagsDict[tag] = 1;
  });

  for (let tag in expectedClosingTagsDict){
    if (expectedClosingTagsDict[tag]  !== actualClosingTagsDict[tag]) return tag.replace(/<|\/|>/g, '');
  }
  return "true";
}

console.log(HTMLElements("<div><b><p>hello world</p></b></div>"));
console.log(HTMLElements("<div><i>hello</i>world</b>"));
console.log(HTMLElements("<div><div><b><b/></div><p/>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));
console.log(HTMLElements("<div><p></p><em><div></div></em></div>"));

Not sure which is the fastest but I'd definitely pick my second or third solution over the first when thinking of performance, space & time complexity, and readability. I think I'd finally pick the third solution over the second one as the third would run in O(n) whereas the second is not guaranteed to run in O(n) but looks more like O(n * m), more akin to quadratic time due to the nested splice in the for-loop. A whole lot more to discuss and factor in here but in the end, you can just do timed tests and pick one over the other really ‍♂️

user_114103230

Here is the python solution for this problem:

import re

def string_check(str):
    opening_tags = ["<br>","<i>","<div>","<a>"]
    closing_tags = ["</br>","</i>","</div>","</a>"]

    stack = []

    tags_list = re.split('(<[^>]*>)', str)[1::2]

    for tag in tags_list:
        if tag in opening_tags:
            stack.append(tag)
        elif tag in closing_tags:
            pos = closing_tags.index(tag)
            if (len(stack) > 0) and (opening_tags[pos] == stack[len(stack)-1]):
                stack.pop()
            else:
                continue
    if stack:
        return stack[-1].replace('<','').replace('>','')
    return True
user_7363270

Using PHP

$div="<div><div><b></b></div></p>";


function sub_str($str, $start, $end)
{
    return substr($str, $start, $end - $start );
}
function find_open_tag($str) {
  
    $open_tags=array(
        "<div>"=>"div",
        "<p>"=>"p",
        "<b>"=>"b",
        "<i>"=>"i",
        "<em>"=>"em",
   
    );
    $closed_tags=array(
        "</div>"=>"<div>",
        "</p>"=>"<p>",
        "</b>"=> "<b>",
        "</i>"=>"<i>",
        "</em>"=>"<em>",
    );
  
    for($i=0;$i<strlen($str);$i++){
        if($open=array_search(sub_str($str,$i,$i+5),$closed_tags)){
            $start=strpos($str,sub_str($str,$i,$i+5)); 
            $end=strpos($str,$open);
            if($end !== false){
                find_open_tag(sub_str($str,$start+5,$end));
            }else {
                return $open_tags[sub_str($str,$i,$i+5)];
            }
            
        }elseif($open=array_search(sub_str($str,$i,$i+4),$closed_tags) ){
            $start=strpos($str,sub_str($str,$i,$i+4)); 
            $end=strpos($str,$open);
            if($end !== false){
                find_open_tag(sub_str($str,$start+4,$end));
            }else {
                return $open_tags[sub_str($str,$i,$i+4)];
            }
        }elseif($open=array_search(sub_str($str,$i,$i+3),$closed_tags) ){
            
            $start=strpos($str,sub_str($str,$i,$i+3)); 
            $end=strpos($str,$open);
            if($end !== false){
                find_open_tag(sub_str($str,$start+3,$end));
            }else {
               
                return $open_tags[sub_str($str,$i,$i+3)];
            }
        }
        
    }
    return false;
}
function StringChallenge($str) {

  
    $closed_tags=array(
        "</div>"=>"<div>",
        "</p>"=>"<p>",
        "</b>"=> "<b>",
        "</i>"=>"<i>",
        "</em>"=>"<em>",
    );

    for($i=0;$i<strlen($str);$i++){
       
        if($open=array_search(sub_str($str,$i,$i+5),$closed_tags)){
            $start=strpos($str,sub_str($str,$i,$i+5)); 
            $end=strpos($str,$open);
            if($value=find_open_tag(sub_str($str,$start+5,$end))){
                return htmlspecialchars($value);
            }
            
            $i=$end;
        }elseif($open=array_search(sub_str($str,$i,$i+4),$closed_tags) ){
            $start=strpos($str,sub_str($str,$i,$i+4)); 
            $end=strpos($str,$open);
            if($value=find_open_tag(sub_str($str,$start+4,$end))){
                return htmlspecialchars($value);
            }
            $i=$end;
        }elseif($open=array_search(sub_str($str,$i,$i+3),$closed_tags) ){
            $start=strpos($str,sub_str($str,$i,$i+3)); 
            $end=strpos($str,$open);
            if($value=find_open_tag(sub_str($str,$start+3,$end))){
                return htmlspecialchars($value);
            }
            $i=$end;
        }
        
    }
    return "true";
  
  }  
// keep this function call here  
echo StringChallenge($div);
user_114301510

Here is an entirely alternate direction if the nodes are properly nested, it removes them until all have been removed (so we know they were all properly nested), OR when it finds not properly nested nodes, it returns the first node that could be changed to rectify the issue.

function HTMLElements(str) {  
  while (str != theThing(str)){
    str = theThing(str);
    if (!str.match("</"))
      return "true";
  }
  const badTag = str.match(/<(\w+?)>[^>]*?<\/\w+?>/);
  return badTag[1];
}
function theThing(str){
  const endTag = str.match(/<\/(\w+?)>/);
  var replace = "<"+endTag[1]+">[^<]*?<."+endTag[1]+">";
  var re = new RegExp(replace,"");
  str = str.replace(re,"");
  return str;
}
// keep this function call here 
console.log(HTMLElements(readline()));
user_194119890
Related