html 如何检查DOM元素是否正确嵌套

du7egjpx  于 2022-11-27  发布在  其他
关注(0)|答案(7)|浏览(165)

我需要帮助来解决这个编码难题。
让函数HTMLElements（str）读取所传递的str参数，该参数将是HTML DOM元素和纯文本的字符串。将使用的元素包括：B、i、em、div、p。例如：如果str是"<div><b><p>hello world</p></b></div>"，那么这个DOM元素的字符串是正确嵌套的，所以程序应该返回字符串true。
如果字符串嵌套不正确，则返回遇到的第一个元素，如果将其更改为其他元素，则会生成格式正确的字符串。如果字符串格式不正确，则只需更改一个元素。例如：如果str是"<div><i>hello</i>world</b>"，那么程序应该返回字符串div，因为如果第一个元素被更改为<b>，字符串将被正确格式化。
例如：
第一个
以下是我的进展：

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>")

现在我明白这远远不能解决问题，但我想这对我来说是一个开始。我最终会解决这个问题，但感谢你的投入

Html

7条答案

按热度按时间
gblwokeq

gblwokeq1#

有几个问题。
首先，你要做closingTag.indexOf(...) === -1，如果它等于-1，就意味着这个结束标记根本没有找到，但是要求是“检测一个问题”，即使结束标记在这里，但是顺序不对 （嵌套不正确）。
因此，您可以做的第一个修正是：

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

这将从结束标记数组的末尾向后计数。因为first开始标记对应于last结束标记。
但是，我们遇到了一个问题。indexOf将返回标签的第次出现。但是，如果我们有多个div标签嵌套在彼此的内部呢？它将不知道你引用的是哪一个。
我的建议是，在开始标签数组中从左到右排列，而在结束标签数组中从右到左排列，而不是使用indexOf。一个简单的方法是对第二个数组使用.reverse()，这样就可以在相同的方向上使用这两个数组：

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
赞(0）分享  回复(0）举报  2022-11-27
u4vypkhs

u4vypkhs2#

我已经研究了一个替代的解决方案，基于blex发布的一个。作为一个说明，这个方法没有考虑标签是否是畸形的，所以可能有必要注意这一点。

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>"));
赞(0）分享  回复(0）举报  2022-11-27
hkmswyz6

hkmswyz63#

进一步研究blex的解决方案，以说明<div>abc</div><p><em><i>test test test</b></em></p>等大小写字符串，其中div标签立即打开和关闭，并且没有任何其他标签嵌套在其中。

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>"));

但是当我更深入地思考这个问题并考虑到**“如果一个字符串没有正确嵌套，返回遇到的第一个元素，如果将其更改为不同的元素，将导致一个格式正确的字符串。如果字符串格式不正确，那么它将只是一个需要更改的元素”**，这个条件确实有帮助，知道它只能是一个没有正确嵌套的元素👌🏾也就是说，我认为更好的解决方案和方法是：

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>"));

另一种方法是使用字典对标签进行频率计数，并对不符合的标签进行比较：

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>"));

我不确定哪一个是最快的，但是考虑到性能、空间和时间复杂性以及可读性，我肯定会选择第二个或第三个解决方案。我想我最终会选择第三个解决方案，因为第三个解决方案可以在O(n)中运行，而第二个解决方案不一定能在O(n)中运行，但看起来更像O(n * m)。由于for循环中的嵌套拼接，更类似于二次时间。这里有很多要讨论和考虑的因素，但最终，你可以只做定时测试，并选择一个超过另一个真的🤷🏾‍♂️

赞(0）分享  回复(0）举报  2022-11-27
ulmd4ohb

ulmd4ohb4#

下面是python对此问题的解决方案：

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
赞(0）分享  回复(0）举报  2022-11-27
z5btuh9x

z5btuh9x5#

使用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);
赞(0）分享  回复(0）举报  2022-11-27
xcitsw88

xcitsw886#

下面是一个完全相反的方向，如果节点嵌套正确，它会删除它们，直到所有节点都被删除（这样我们就知道它们都是正确嵌套的），或者当它发现嵌套不正确的节点时，它会返回第一个可以更改的节点来纠正问题。

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()));
赞(0）分享  回复(0）举报  2022-11-27
bkkx9g8r

bkkx9g8r7#

下面是使用Stack而不是regex的另一种方法。
1.我们想创建一个方法converStringToList。这将需要作为使用regex的替换。
1.然后在htmlElements方法中，我想示例化一个堆栈，一个openTags和closeTags的数组，一个名为res的字符串和converStringToList。
1.我们迭代converStringToList并检查current是否为openTag，如果是，则压入堆栈。
1.如果current是closeTag，并且openTag中堆栈peek的索引等于closeTag中current的索引，则将其从堆栈中弹出，因为它们匹配
1.如果current是一个closeTag，并且openTag中的stack peek的索引不等于closeTag中的current的索引，则我们满足条件并返回stack peek。
htmlElement方法

public static String htmlElements (String str) {
        List<String> list = convertStringToList(str);
        Stack<String> stack = new Stack<>();
        String[] openTags = {"<br>", "<i>", "<div>", "<a>", "<p>", "<em>", "<b>"};
        String[] closeTags = {"</br>", "</i>", "</div>", "</a>", "</p>", "</em>", "</b>"};
        String res = "";

        for (String s : list) {
            if (Arrays.asList(openTags).contains(s)) {
                stack.push(s);
            } else if (
                    Arrays.asList(closeTags).contains(s) &&
                    Arrays.asList(openTags).indexOf(stack.peek()) ==
                    Arrays.asList(closeTags).indexOf(s)
            ) {
                stack.pop();
            } else if (
                    Arrays.asList(closeTags).contains(s) &&
                    Arrays.asList(openTags).indexOf(stack.peek()) !=
                    Arrays.asList(closeTags).indexOf(s)
            ) {
                res = stack.peek();
                break;
            }

        }

        return res;
    }

converStringToList方法

public static List<String> convertStringToList(String str) {
        List<String> list = new ArrayList<>();

        int left, right,  i = 0;
        int n = str.length();

        while (i < n) {

            if (str.charAt(i) == '<') {
                right = i;
                while (str.charAt(right) != '>') {
                    right++;
                }
                right++;
                list.add(str.substring(i, right));
            }

            if (i > 0 && str.charAt(i - 1) == '>' && str.charAt(i) != '<') {
                left = i;
                while (str.charAt(left) != '<') {
                    left++;
                }
                list.add(str.substring(i, left));
            }

            i++;
        }

        return list;
    }
赞(0）分享  回复(0）举报  2022-11-27
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com