求解一道xml parser的题

看到一个面经说

一个string paring问题： “<ClassA><PropertyA>valueA</PropertyA><PropertyB>ValueB</PropertyB>...</ClassA>   <ClassA><PropertyA>...</PropertyA><PropertyB>...</PropertyB>...</ClassA>...”， 然后print出一个表格
PropertyA PropertyB ...
ValueA      ValueB ...
Property 提前并没有定义，要看到时候parse出来是啥

我理解是这个string应该是有类似<div></div>在开头结尾的。但是实在想不到怎么去parse这种string？是建一个类似下面这样的tag class，然后用stack？

class Tag {
  String name;
  String value;
  List<Tag> children
}

你的思路感觉可以。碰到tag开头就入栈tag的下表，碰到tag结尾就出盏并且把盏顶坐标到当前坐标中间的值记录成value。感觉也可以用dfs来做。个人感觉dfs可能会简单点。dfs返回一个dom tree的节点（就像你定义的一样）就可以了。

hjy 发表于 2020-10-26 14:08
你的思路感觉可以。碰到tag开头就入栈tag的下表，碰到tag结尾就出盏并且把盏顶坐标到当前坐标中间的值记录 ...

谢谢！感觉实际做parsing的时候有点tricky, 要判断‘<’ ‘>’还有value。另外后面把信息打出来也是有点乱，只能从parent tag再做一次dfs？

下面这个是sudo code， 我感觉可以试试这样：

sudo code:

1. def dfs(node, str, idx):
   
2. initialize a buffer stack
   
3.       i = idx
   
4.     while (i < len(str)):
   
5.         if str[i] is '<':
   
6.             push i onto stack
   
7.             i++
   
8.         else if str[i] is '>':
   
9.             peek stack top store that as j, tag_name = str[j+1,i]
   
10.             if the tag_name starts with "/":
    
11.                 pop stack top
    
12.                 peek stack top as k
    
13.                 str [k+1, j] is the value of the current tag
    
14.                 set tag name and value of the current node(don't set the value if current node's child list is not empty)
    
15.                 return node, i+1
    
16.             else:
    
17.                 if i + 1 < str.length and str[i+1] == '<':
    
18.                     childnode, nextidx = dfs(new node(), str, i+1)
    
19.                     i = nextidx
    
20.                     add childnode to current child list
    
21.                 else:
    
22.                     push i to stack
    
23.                     i ++
    
24.         else:
    
25.             i++
    
26.     return node, i+1

复制代码

[/i][/i]