SGF 解析

说明

解析一个 Smart Game Format 字符串。

SGF 是存储棋类游戏文件的标准格式，尤其是围棋。

SGF 是一种相当简单的格式。一个 SGF 文件通常包含一棵节点树，每个节点都是一个属性列表。属性列表由键值对组成，每个键只能出现一次，但可以有多个值。

这道练习会要求你解析一个 SGF 字符串，并返回一个由属性构成的树形结构。

一个 SGF 文件可能长这样：

(;FF[4]C[root]SZ[19];B[aa];W[ab])

这是一棵包含三个节点的树：

• 顶层节点有三个属性：FF[4]（键 = “FF”，值 = “4”）、C[root]（键 = “C”，值 = “root”）和 SZ[19]（键 = “SZ”，值 = “19”）。（FF 表示 SGF 的版本，C 是注释，SZ 是棋盘的大小。）
  • 顶层节点有一个唯一的子节点，该子节点只有一个属性：B[aa]。（黑棋下在编码为 “aa” 的点上，也就是 1-1 点。）
    • B[aa] 节点有一个唯一的子节点，该子节点只有一个属性：W[ab]。

可以想象，一个 SGF 文件中会有很多只有一个子节点的节点，这就是它有一套简写形式的原因。

SGF 可以表示下法的变化。围棋棋手在复盘时会做大量回溯（试试这步，不行，再试试那步），SGF 支持下法序列的各种变化。例如：

(;FF[4](;B[aa];W[ab])(;B[dd];W[ee]))

这里根节点有两个变化。第一个（按惯例表示实际下出的着法）是黑棋下在 1-1。黑棋的老师把这份文件发给了他，并指出根节点第二个子节点中有一手更合理的下法：B[dd]（4-4 点，一个非常标准的占角开局）。

一个键可以关联多个值。例如：

(;FF[4];AB[aa][ab][ba])

这里用 AB（添加黑子）在棋盘上添加了三颗黑子。

所有属性值都将采用 SGF Text 类型。你无需实现任何其他值类型。你可以阅读 Text 类型的完整文档，下面是几个要点的总结：

• 换行符如果紧跟在 \ 之后，就会被删除，否则仍然作为换行符保留。
• 除换行符之外的所有空白字符都会转换为空格。
• \ 是转义字符。\ 之后的任何非空白字符都会按原样插入。\ 之后的任何空白字符都遵循上面的规则。注意，SGF 没有针对 \t 或 \n 等空白字符的转义序列。

注意不要混淆以下两者：

• 测试中字符串字面量所表示的字符串
• 传递给 SGF 解析器的字符串

字符串字面量中的转义序列在被传递给 SGF 解析器之前，可能已经由编程语言的解析器处理过了。

SGF（以及解析本身）还有一些更复杂的地方，你基本上可以忽略。你可以假定输入采用 UTF-8 编码，测试中不会包含 charset 属性，所以不用担心这一点。此外，你可以假定所有换行符都是 Unix 风格（\n，测试中不会出现 \r 或 \r\n），并且测试中不会包含属性、节点等之间的多余空白。