Parse XML Tree
如今有一个Tokenizer，返回的Token都是XML标签或许内容，比方
(open, html)(inner, hello)(close, html)示意<html>hello</html>，每个括号及其内容是一个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文件的代码实例的细致内容，更多请关注ki4网别的相干文章！
