确定正确 html 标签关闭的算法

Question

我正在 JAVA 中编写自己的 HTML 解析器实现。到目前为止，我已经完成了词法分析器并继续编写解析器。我正在创建 DOM 树，我想确定我的 HTML 是否构建正确。

例如，我有一个 img 标签，它是一个 void 标签基于 w3 org html syntax

而且不需要结束标签。

另一方面，大多数像body、head这样的标签必须有它的结束标记。

我的问题是：处理这个问题的正确方法是什么？

我不需要工具或任何外部站点来确定，我想问的是什么方法可以确定。

Answer 1

您正在处理 HTML，因此标签集非常有限。您可以轻松跟踪标签是否为 void 标签。

对于其余的标签，我建议采用以下算法：

获取下一个标签。 (a) 如果它是一个开始标签，例如，只需将其推入 Stack。 (b) 如果是结束标签，则转到步骤 2。 (c) 如果没有更多的标签需要解析，那么你的 HTML 是有效的。
从堆栈中弹出标签 one-by-one。 (a) 如果您在到达当前标签的开始对之前在堆栈上遇到另一个 开始标签，那么您的 HTML 结构已损坏。 (b) 如果您清空堆栈并且仍然没有一对到您当前的 结束标记 ，那么您的 HTML 又是损坏的。 (c) 如果您遇到当前标签的 opening pair 避免情况 (a) 和 (b)。转到步骤 1。

这是一个粗略的 pseudo-code，但我希望您能理解。如果需要，我可以在 Java/C# 中编写实现。

Answer 2

这是很多软件公司的经典"job interview problem"。它是关于检查字符串（在这种情况下，您的 HTML 代码）是否相对于某些字符（在这种情况下，HTML 标签）是平衡的。使用 Stack 解决了这个问题。当您处理字符串时，对于每个开始标记，您调用一个 "push" 操作。对于每个结束标记，您调用一个 "pop" 操作。如果在处理结束时 Stack 为空（并且在分析过程中未发现错误），您的 HTML 代码将被平衡。下面的函数检查一个字符串在括号方面是否平衡。

private boolean isBalanced(String s) {

    Stack symbolStack = new Stack();

    for(int i = 0; i < s.length(); i++) { //Processing the input string ...

        char c = s.charAt(i);

        if(c == '(') { //If the character is an opening parenthesis --> push

            symbolStack.push(c);
        }
        else if(c == ')') { //If the character is a closing parenthesis ...

            if(symbolStack.isEmpty()) { //Error: the stack is empty
                return false;
            }
            else {
                char c2 = (char) symbolStack.pop();

                if(c2 != '(') { //Error: no opening parenthesis in the stack
                    return false;
                }
            }
        }
    }

    if(symbolStack.isEmpty()) { //No error and empty stack --> balanced string
        return true;
    }

    return false;
}

确定正确 html 标签关闭的算法

Algorithm to determine proper html tag closing

html

java

tags

algorithm

parsing