|
|---|
|
|
|
|
|
|
g**********9
发帖数: 49 | 1 have a flat xml string:
n1n2n3n4
How to convert it into a tree structure below. Suppose you have a XML parser
can tell you getNextTag(); isTagStartingNode(); isTagEndNode(); isTagString
()
n1
/
n2
/ \
n3 n4
Any idea? | a***w
发帖数: 168 | 2 有点思路，问一下isTagString是什么意思？ | f*******b
发帖数: 520 | 3 没细想，大概思路是：
while(tag.getNextTag()!=null)
{
if(tag.getNextTag()==StartingNode)
tag=tag.getNextTag();
if(tag.getNextTag().getNextTag()==String)//节点进一层，level+1,之前节点为此
节点的母节点
Mother[Level]=tag;
Mother[Level++].CreatChild();
Tag=Tag.getNextTag().getNextTag();
if(tag.getNextTag().getNextTag()==StartingNode)//节点在同层,level不变，母节
点不变
Tag.getNextTag().getNextTag().getNextTag()
Mother[Level].CreatChild();
if(tag.getNextTag().getNextTag()==EndNode） //节点退一层，level-1，母节点回
溯到上层母节点
Level--；
if(tag.getNextTag()==EndNode)
if(level==0)//最后节点退出
return;
else
tag=tag.getNextTag();
} | s*******s
发帖数: 1031 | 4 我的代码，用递归做。不一定对 。。
// n1n2n3n4
n1
/
n2
/ \
n3 n4
string getNextTag();
bool isTagStartingNode(string tag);
bool isTagEndNode(string tag);
bool isTagString(string tag)
struct TreeNode {
string value;
TreeNode *left;
TreeNode *right;
TreeNode(string v) : value(v), left(NULL), right(NULL) {}
};
TreeNode *parse(string startTag) {
// no more nodes left
if(str.size() == 0)
return NULL;
if(startTag.size() == 0) {
string str = getNextTag();
// invalid input?
if(!isTagStartingNode(str))
return NULL;
return parse(str);
} else if(isTagString(str)) {
TreeNode *root = new TreeNode(str);
string nextStr = getNextTag();
if(isTagStartingNode(nextStr)) {
root->left = parse(nextStr);
nextStr = getNextTag();
if(isTagEndNode(nextStr)) {
root->right = NULL;
return root;
} else {
root->left = parse(nextStr);
}
nextStr = getNextTag();
if(!isTagEndNode(nextStr)) {
// input error
throw "error";
}
return root;
} else if(isTagEndNode(nextStr)) {
return root;
} else {
// input error
throw "error";
}
} else {
// input error
throw "error";
}
}
parser
isTagString
【在 g**********9 的大作中提到】
: have a flat xml string:
: n1n2n3n4
: How to convert it into a tree structure below. Suppose you have a XML parser
: can tell you getNextTag(); isTagStartingNode(); isTagEndNode(); isTagString
: ()
: n1
: /
: n2
: / \
: n3 n4
| x****8
发帖数: 127 | 5 stack?
public static void main(String[] args) {
XmlParser p = new XmlParser("ABDC");
String s;
Stack> stk = new Stack>();
TreeNode root = null;// = new TreeNode();
while((s = p.getNextTag()) != null){
if(p.isStartTag()){
String str = p.getNextTag();//assert is string tag
TreeNode node = new TreeNode(str);
if(stk.isEmpty()){
root = node;
}else{
TreeNode parent = stk.peek();
if(parent.left == null){
parent.left = node;
}else{
parent.right = node;
}
}
stk.push(node);
}else if(p.isEndTag()){
stk.pop();
}
}
}
public class XmlParser{
public int pos;
public String str;
public XmlParser(String s){
this.str = s;
}
private int curType = 0;//0:start, 1: end, 2:string
public boolean isStringTag(){
return curType == 2;
}
public boolean isStartTag(){
return curType == 0;
}
public boolean isEndTag(){
return curType == 1;
}
public String getNextTag(){
if(pos >= str.length()){
return null;
}
String tag = null;
int end = -1;
if(str.charAt(pos) == '<'){
if(str.charAt(pos + 1) != '/'){
end = str.indexOf('>', pos + 1);
curType = 0;
tag = str.substring(pos + 1, end);
}else{
pos++;
end = str.indexOf('>', pos + 1);
curType = 1;
tag = str.substring(pos + 1, end);
}
}else{
end = str.indexOf('<', pos) - 1;
curType = 2;
tag = str.substring(pos, end + 1);
}
pos = end + 1;
return tag;
}
}
parser
isTagString
【在 g**********9 的大作中提到】
: have a flat xml string:
: n1n2n3n4
: How to convert it into a tree structure below. Suppose you have a XML parser
: can tell you getNextTag(); isTagStartingNode(); isTagEndNode(); isTagString
: ()
: n1
: /
: n2
: / \
: n3 n4
| c********p
发帖数: 1969 | |
|
|
|
|
|
|
|
