[Algo] Parse XML Tree 解析XML文件

liuyix 發布于2019-08-14 16:16 / 1923人閱讀

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

Parse XML Tree

現在有一個Tokenizer，返回的Token都是XML標簽或者內容，比如(open, html)(inner, hello)(close, html)表示hello，每一個括號及其內容是一個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 stk = new Stack();
        // 將第一個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 children;
    
    XMLNode(String type, String value){
        this.type = type;
        this.value = value;
        this.children = new ArrayList();
    }
}

云服務器 GPU云服務器 xml文件解析解析xml文件 java 解析xml文件 dom4j解析xml文件

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66182.html

基于機器學習的DAG調度平臺

摘要：算子背后是實現的一些算法組件機器學習前端交互機器學習平臺前端主要是將機器學習的流程裝成一個，定義各個算子的出入參，以及算子的配置參數，組裝成一個文件，傳給調圖平臺是方式交互，是通過文件定義，通過。什么是DAG? 有向無環圖樹形結構：除根節點，每個節點有且僅有一個上級節點，下級節點不限。根節點沒有上級節點。圖結構：每個節點上級、下級節點數不限。 DAG調度平臺的定義及場景任務調度...

LucasTwilight 2019-07-31 11:07 評論0 收藏0
在XMLSignature中使用BouncyCastle做RSA

Abstract There is an article shows demo code for making XMLSignature by using Java XML Digital Signature API, where it actually uses org.jcp.xml.dsig.internal.dom.XMLDSigRI to do DOM formation, and th...

LiangJ 2019-08-19 11:07 評論0 收藏0
Spring解密 - 自定義標簽與解析

摘要：自定義標簽在講解自定義標簽解析之前，先看下如何自定義標簽定義文件定義一個文件描述組件內容聲明命名空間值得注意的是與可以是不存在，只要映射到指定就行了。 Spring是一個開源的設計層面框架，解決了業務邏輯層和其他各層的松耦合問題，將面向接口的編程思想貫穿整個系統應用，同時它也是Java工作中必備技能之一... 前言在上一節 Spring解密 - 默認標簽的解析中，重點分析了...

Taste 2019-08-15 13:40 評論0 收藏0
XML Notebook

摘要：不使用外部聲明屬性單雙引號皆可大小寫敏感大小寫不敏感必須有根元素實體引用實體任何包含數據的項實體中要使用轉義字符無論寫什么，都當作普通文本逐行掃描，邊掃描邊解析，速度快不能對節點進行修改構造，方便遍歷和修改對于大文件，內存壓力大獲取子 XML: EXtensible Markup Language 1. Basic Syntax 1.1 Processing instruction ...

darkbug 2019-08-27 10:56 評論0 收藏0