[Algo] Parse XML Tree 解析XML文件

liuyix 发布于2019-08-14 16:16 / 1925人阅读

摘要：现在有一个，返回的都是标签或者内容，比如表示，每一个括号及其内容是一个，请问如何表示这个文件。栈法复杂度时间空间思路这题首先要想清楚的是，如何表示，因为是典型的一父多子，我们用树来表示比较好。如果是一个的，则把上一层节点弹出栈。

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文件

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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