構文解析

今日は久しぶりにコードを書いた。 そして今まで敬遠してきた構文解析を勉強。

tanakhさんという方が「10分で書ける、お手軽パーザー」を公開されているので、これをもとに PKU の 1460 Firefighters を解きました。

問題を解くにあたっては、キモとなる部分は出来ているので流用させてもらい（まんまパクリだ）、エラー処理と式を作るとこだけ書きました。それでも解けずに数十分悩んでたあたりダメダメだ…。あと int じゃ足りないかと思って long long にしたのは無駄だった。

問題内容は、式と整数値が与えられるので、式を計算したらその整数値になるかどうか判定しろという話。ただし、一部の演算子が ? になっていることがあり、ここには + - * / のどれが入るか分からない。そこでどれかを入れて一つでも式の値が与えられた整数値に一致すれば良しとする。一つの式に ? は最大 10 個まで存在し得る（→全探索。 4¹⁰ = 2²⁰ で約 100 万だし）。

シンタックスエラーは無いと問題文で述べてるので、気を付けるのはゼロ割りなどのエラー対処くらい。でも、「parsed 型の解析し残した文字列が NULL の時はエラー」という扱いで書いてたんですが、これを一ヶ所だけチェックし忘れていたせいで何度も RE …という感じでハマりました。

確か数年前の ICPC 国内大会で、原子量と分子式から分子量を計算しろという問題があったと思うので、近いうちにやっておこう…。