Parse XML Tree

Now there is a Tokenizer, and the returned Tokens are XML tags or content, such as (open, html)(inner, hello) (close, html) means <html>hello</html>. Each bracket and its content is a Token. How to represent this XML file.

Stack method

Complexity

Time O(N) Space O(N)

Thinking

This question The first thing to think about clearly is how to represent XML. Because XML is a typical one-parent-multiple-child model, it is better to use a tree to represent it. Then analyze how to use Tokenizer. Tokenizer is a bit like Iterator. Whenever we use Tokenizer to get a Token, if it is an Open Token, we need to create a new node. There may also be new nodes under this new node. If it is an Inner Token, we also need to create a new node, but there will be no new nodes under this node. If it is a Close Token, we do not need new nodes, and we need to ensure that the previous Open node no longer accepts new nodes, and the new nodes must be attached to the nodes of the previous layer. Here, we use the stack to retain the node information of the previous layer to help us build the tree. If this is an Open Token, we need to create a new node and add it behind the previous node and add it to the stack. If it is an Inner Token, we also need to create a new node and add it behind the previous node, but not add it to the stack. If it is a Close Token, pop the previous node from the stack.

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

Copy after login

The above is the detailed content of Parse XML Tree code example for parsing XML files. For more information, please follow other related articles on the PHP Chinese website!