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），而且測試中屬性、節點等之間不會有多餘的空白。