使用规则将字符串转换为树表示

Question

我要做一些简单的RTF文本解析,我需要纠正一个问题.给出以下字符串:

{aaaaaaa\}aaaa\{aaaaa{bbbbbbbb{ccccc\{cccc}bbb{eeeee}{{gggg}ffff}bbbbbb}aaaaa}

哪里:

\ means ignore next character
{ means expand
} means collapse up to parent

在字符串中的任何位置,除了封闭标签中的字符之外,状态可能会受到任何前一个字符的影响.例如{gggg}不会影响ffff,但aaaaaaa aaa ..会影响bbbb, ccc, eee, ggg, fff等等.

由此我们可以将上面的内容拆分为有意义的块

A1 = aaaaaaa\}aaaa\{aaaaa
B1 = bbbbbbbb
C = ccccc\{cccc
B2 = bbb
E = eeeee
G = gggg
F = ffff
B3 = bbbbbb
A2 = aaaaa

产量:

{A1{B1{C}B2{E}{{G}F}B3}A2}

为了描述我使用的依赖关系X> Y意味着Y依赖于X(如在X中可能改变Y的含义)

A1
A1 > B1
A1 > B1 > C
A1 > B1 > B2
A1 > B1 > B2 > E
A1 > B1 > B2 > G
A1 > B1 > B2 > F
A1 > B1 > B2 > B3
A1 > B1 > B2 > A2
A1 > A2

因此,如果我们有一个节点可以有一个值和一个有序的子值列表.这样值树看起来像这样:

A1
- B1
- - C
- - B2
- - - E
- - - G
- - - F
- - - B3
- A2

然后,为了获得影响任何节点的字符,我可以递归地逐步遍历每个父节点.

我一直坚持的是尝试将字符串解析为我的节点类:

public class myNode
{
    public myNode Parent;
    public string Value;
    public List<myNode> subNodes;
}

当我遇到\I增加2 时,我逐个字符地读取字符串.当我遇到一个{我保存前一个文本部分作为节点值并进入孩子时,当我遇到一个}我下台.

但我一直在弄乱逻辑,特别是对于G和A2.它在纸上做起来很简单,但是当我尝试执行降压的实际逻辑时,我一直在弄乱它.

是否有更直接的方式来制作这种结构？(或者我应该使用更好的结构).我认为应该有一些库允许将字符串转换为树,但我似乎无法找到任何.

Answer 1

使用"状态机"方法,其中状态是当前节点,以及转义标志:

string rtf = @"{aaaaaaa\}aaaa\{aaaaa{bbbbbbbb{ccccc\{cccc}bbb{eeeee}{{gggg}ffff}bbbbbb}aaaaa}";

Node root = new Node { Parent = null, Value = "root", SubNodes = new List<Node>() };
Node node = root;
bool escape = false;
foreach (char c in rtf) {
  if (escape) {
    node.Value += c;
    escape = false;
  } else {
    switch (c) {
      case '{':
        node = new Node { Parent = node, Value = String.Empty, SubNodes = new List<Node>() };
        node.Parent.SubNodes.Add(node);
        break;
      case '}':
        node = new Node { Parent = node.Parent.Parent, Value = String.Empty, SubNodes = new List<Node>() };
        if (node.Parent != null) node.Parent.SubNodes.Add(node);
        break;
      case '\\':
        escape = true;
        break;
      default:
        node.Value += c;
        break;
    }
  }
}

PrintNode(root, String.Empty);

Node类(刚刚重命名):

public class Node {
  public Node Parent;
  public string Value;
  public List<Node> SubNodes;
}

用于显示:

private static void PrintNode(Node node, string level) {
  if (node.Value.Length > 0) Console.WriteLine(level + node.Value);
  foreach (Node n in node.SubNodes) {
    PrintNode(n, level + "  ");
  }
}

输出:

root
  aaaaaaa}aaaa{aaaaa
    bbbbbbbb
      ccccc{cccc
    bbb
      eeeee
        gggg
      ffff
    bbbbbb
  aaaaa

请注意,G节点不是E节点的子节点,而是具有空值的节点的子节点.

当然,您还必须添加一些错误处理.