首頁  >  文章  >  後端開發  >  Parse XML Tree 解析XML檔案的程式碼實例

Parse XML Tree 解析XML檔案的程式碼實例

黄舟
黄舟原創
2017-03-17 16:58:552007瀏覽

Parse XML Tree

現在有一個Tokenizer,回傳的Token都是XML標籤或是內容,例如(open, html)(inner, hello) (close, html)表示100db36a723c770d327fc0aef2ce13b1hello73a6ac4ed44ffec12cee46588e518a5e,每一個括號及其內容是一個Token,請問如何表示這個XML檔。

堆疊法則

複雜度

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

想法

這題首先要想清楚的是,如何表示XML,因為XML是典型的一父多子,我們用樹來表示​​比較好。然後分析下如何用Tokenizer,Tokenizer有點像Iterator,每當我們用Tokenizer拿到一個Token時,如果這是一個Open的Token,我們需要新建一個節點,這個新節點下面也有可能有新節點。如果是Inner的Token,我們也需要新建一個節點,但這個節點下面不會有新的節點。如果是一個Close的Token,我們不需要新節點,而且需要確保上一個Open節點不再接納新節點了,而對於新節點則要附在上一層的節點後面。這裡,我們用棧可以保留上一層的節點訊息,幫助我們建造一棵樹。如果這是Open的Token,我們需要新建一個節點加入上一層節點後面,並加入堆疊中。如果是Inner的Token,我們也需要新建一個節點加到上一層節點後面,但不加入堆疊中。如果是一個Close的Token,則把上一層節點彈出堆疊。

代碼

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

   

##

以上是Parse XML Tree 解析XML檔案的程式碼實例的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn