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