栈法复杂度时间 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文件的代码实例的详细内容。