[Algo] Parse XML Tree 解析XML文件

liuyix 發(fā)布于2019-08-14 16:16 / 1927人閱讀

摘要：現(xiàn)在有一個，返回的都是標簽或者內(nèi)容，比如表示，每一個括號及其內(nèi)容是一個，請問如何表示這個文件。棧法復(fù)雜度時間空間思路這題首先要想清楚的是，如何表示，因為是典型的一父多子，我們用樹來表示比較好。如果是一個的，則把上一層節(jié)點彈出棧。

Parse XML Tree

現(xiàn)在有一個Tokenizer，返回的Token都是XML標簽或者內(nèi)容，比如(open, html)(inner, hello)(close, html)表示hello，每一個括號及其內(nèi)容是一個Token，請問如何表示這個XML文件。

棧法 復(fù)雜度

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

思路

這題首先要想清楚的是，如何表示XML，因為XML是典型的一父多子，我們用樹來表示比較好。然后分析下如何用Tokenizer，Tokenizer有點像Iterator，每當我們用Tokenizer拿到一個Token時，如果這是一個Open的Token，我們需要新建一個節(jié)點，這個新節(jié)點下面也有可能有新節(jié)點。如果是一個Inner的Token，我們也需要新建一個節(jié)點，但這個節(jié)點下面不會有新的節(jié)點。如果是一個Close的Token，我們不需要新節(jié)點，而且需要保證上一個Open節(jié)點不再接納新節(jié)點了，而對于新節(jié)點則要附在上一層的節(jié)點后面。這里，我們用棧可以保留上一層的節(jié)點信息，幫助我們建樹。如果這是一個Open的Token，我們需要新建一個節(jié)點加入上一層節(jié)點后面，并加入棧中。如果是一個Inner的Token，我們也需要新建一個節(jié)點加到上一層節(jié)點后面，但不加入棧中。如果是一個Close的Token，則把上一層節(jié)點彈出棧。

代碼

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 stk = new Stack();
        // 將第一個open節(jié)點作為根節(jié)點壓入棧中
        XMLNode root = convertTokenToTreeNode(tknz.nextToken());
        stk.push(root);
        while(!stk.isEmpty()){
            if(!tknz.hasMoreTokens()){
                break;
            }
            XMLNode curr = convertTokenToTreeNode(tknz.nextToken());
            // 得到上一層節(jié)點
            XMLNode father = stk.peek();
            // 根據(jù)當前節(jié)點的類型做不同處理
            switch(curr.type){
                // 對于Open節(jié)點，我們把它加入上一層節(jié)點的后面，并加入棧中
                case "open":
                    father.children.add(curr);
                    stk.push(curr);
                    break;
                // Close節(jié)點直接把上一層Pop出來就行了，這樣就不會有新的節(jié)點加到上一層節(jié)點后面    
                case "close":
                    stk.pop();
                    break;
                // Inner節(jié)點只加到上一層節(jié)點后面    
                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 children;
    
    XMLNode(String type, String value){
        this.type = type;
        this.value = value;
        this.children = new ArrayList();
    }
}