言語処理100本ノック 2015のQ59でS式の解析の問題に出会ったので、パーサの自作なるものにチャレンジしたく、書いてみました。
前提
タスク
以下のS式を多分木にパースします。
(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))
わかりやすいように改行を入れると以下のようになります。
(a (b (d (i) (j) ) (e) (f (k) ) ) (c (g) (h (l (n) ) (m) ) ) )
木にすると以下なイメージです。
実装
Tree
まず、多分木を以下のように定義します。
type Tree struct { Parent *Tree Child []*Tree Value string }
root node
root nodeは親を持たないので、便宜的に自分自身を親として、コンストラクタを書きます。
func NewTree() *Tree { t := &Tree{} t.Parent = t return t }
実装
パーサの実装は以下です。
gistb526d47b5f834803b8d69ce4ccecbc63
Install
githubにあげてあるので以下でInstallできます。
# go get github.com/cipepser/goSExpression-sample/gose
Usage
以下のようにParse()
でパースできます。
s := `(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))` t, err := gose.Parse(s) if err != nil { log.Fatal(err) }
結果の表示は簡易的ですが、以下のようにWalk()
でできるようにしました。
// t.Walk() I am ' a ' my parent is ' a ' ------- I am ' b ' my parent is ' a ' ------- I am ' d ' my parent is ' b ' ------- I am ' i ' my parent is ' d ' ------- I am ' j ' my parent is ' d ' ------- I am ' e ' my parent is ' b ' ------- I am ' f ' my parent is ' b ' ------- I am ' k ' my parent is ' f ' ------- I am ' c ' my parent is ' a ' ------- I am ' g ' my parent is ' c ' ------- I am ' h ' my parent is ' c ' ------- I am ' l ' my parent is ' h ' ------- I am ' n ' my parent is ' l ' ------- I am ' m ' my parent is ' h ' -------