Parse XML Tree

a maintenant un Tokenizer, et les jetons renvoyés sont des balises ou du contenu XML, tels que (open, html)(inner, hello)(close, html) signifie <html>hello</html>, chaque support et son Le contenu est un jeton. Comment représenter ce fichier XML.

Méthode de pile

Complexité

Temps O(N) Espace O(N)

Pensée

Cette question Le La première chose à laquelle il faut réfléchir clairement est de savoir comment représenter XML. Étant donné que XML est un modèle typique à un parent et à plusieurs enfants, il est préférable d'utiliser un arbre pour le représenter. Analysez ensuite comment utiliser Tokenizer. Tokenizer est un peu comme Iterator. Chaque fois que nous utilisons Tokenizer pour obtenir un jeton, s'il s'agit d'un jeton ouvert, nous devons également créer de nouveaux nœuds sous ce nouveau nœud. S'il s'agit d'un jeton interne, nous devons également créer un nouveau nœud, mais il n'y aura pas de nouveaux nœuds sous ce nœud. S'il s'agit d'un jeton fermé, nous n'avons pas besoin de nouveaux nœuds et nous devons nous assurer que le nœud ouvert précédent n'accepte plus de nouveaux nœuds et que les nouveaux nœuds doivent être attachés aux nœuds de la couche précédente. Ici, nous utilisons la pile pour conserver les informations sur les nœuds de la couche précédente afin de nous aider à construire l'arborescence. S'il s'agit d'un jeton ouvert, nous devons créer un nouveau nœud, l'ajouter derrière le nœud précédent et l'ajouter à la pile. S'il s'agit d'un jeton interne, nous devons également créer un nouveau nœud et l'ajouter derrière le nœud précédent, mais pas l'ajouter à la pile. S'il s'agit d'un jeton de fermeture, supprimez le nœud précédent de la pile.

Code

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>();
    }
}

Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!