求解一道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:

[Python] 纯文本查看 复制代码

def dfs(node, str, idx):
initialize a buffer stack
      i = idx
    while (i < len(str)):
        if str[i] is '<':
            push i onto stack
            i++
        else if str[i] is '>':
            peek stack top store that as j, tag_name = str[j+1,i]
            if the tag_name starts with "/":
                pop stack top
                peek stack top as k
                str [k+1, j] is the value of the current tag
                set tag name and value of the current node(don't set the value if current node's child list is not empty)
                return node, i+1
            else:
                if i + 1 < str.length and str[i+1] == '<':
                    childnode, nextidx = dfs(new node(), str, i+1)
                    i = nextidx
                    add childnode to current child list
                else:
                    push i to stack
                    i ++ 
        else:
            i++
    return node, i+1