XML ツリーを解析します

返されるトークンはすべて XML タグまたはコンテンツです (
)。各括弧とそのコンテンツは、この XML ファイルを表す方法です。 (open, html)(inner, hello)(close, html)表示<html>hello</html>

スタックメソッド

複雑さ

時間O(N) 空間O(N)

思考

この質問について最初に明確に考える必要があるのは、XMLをどのように表現するかということです。XMLは典型的な片親であるためです。 -multiple-child モデルを表現するにはツリーを使用することをお勧めします。次に、Tokenizer の使用方法を分析します。Tokenizer を使用してトークンを取得するときは常に、この新しいノードの下に新しいノードを作成する必要があります。内部トークンの場合は、新しいノードを作成する必要もありますが、このノードの下には新しいノードは存在しません。クローズトークンの場合、新しいノードは必要ありません。前のオープンノードが新しいノードを受け入れないようにする必要があり、新しいノードは前の層のノードに接続する必要があります。ここでは、スタックを使用して前の層のノード情報を保持し、ツリーの構築に役立てます。これがオープントークンの場合は、新しいノードを作成し、前のノードの後ろに追加してスタックに追加する必要があります。内部トークンの場合は、新しいノードを作成して前のノードの後ろに追加する必要がありますが、スタックには追加しません。クローズトークンの場合は、スタックから前のノードをポップします。

コード

public class XMLParser {
    
    public static void main(String[] args){
        XMLParser xml = new XMLParser();
        XMLNode root = xml.parse("(open,html)(open,head)(inner,welcome)(close,head)(open,body)(close,body)(close,html)");
        xml.printXMLTree(root, 0);
    }
    
    public XMLNode parse(String str){
        // 以右括号为delimiter
        StringTokenizer tknz = new StringTokenizer(str, ")");
        Stack<XMLNode> stk = new Stack<XMLNode>();
        // 将第一个open节点作为根节点压入栈中
        XMLNode root = convertTokenToTreeNode(tknz.nextToken());
        stk.push(root);
        while(!stk.isEmpty()){
            if(!tknz.hasMoreTokens()){
                break;
            }
            XMLNode curr = convertTokenToTreeNode(tknz.nextToken());
            // 得到上一层节点
            XMLNode father = stk.peek();
            // 根据当前节点的类型做不同处理
            switch(curr.type){
                // 对于Open节点，我们把它加入上一层节点的后面，并加入栈中
                case "open":
                    father.children.add(curr);
                    stk.push(curr);
                    break;
                // Close节点直接把上一层Pop出来就行了，这样就不会有新的节点加到上一层节点后面    
                case "close":
                    stk.pop();
                    break;
                // Inner节点只加到上一层节点后面    
                case "inner":
                    father.children.add(curr);
                    break;
            }
        }
        return root;
    }
    
    private XMLNode convertTokenToTreeNode(String token){
        token = token.substring(1);
        String[] parts = token.split(",");
        return new XMLNode(parts[0], parts[1]);
    }
    
    private void printXMLTree(XMLNode root, int depth){
        for(int i = 0; i < depth; i++){
            System.out.print("-");
        }
        System.out.println(root.type + ":" + root.value);
        for(XMLNode node : root.children){
            printXMLTree(node, depth + 1);
        }
    }
}

class XMLNode {
    String type;
    String value;
    List<XMLNode> children;
    
    XMLNode(String type, String value){
        this.type = type;
        this.value = value;
        this.children = new ArrayList<XMLNode>();
    }
}

ログイン後にコピー

以上がXML ファイルを解析するための XML ツリーの解析コード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。