天下一プログラマーコンテスト2015予選B - 天下一リテラル
Published on 2024-02-28Last Modified 2024-02-28
Table Of Contents
問題概要
問題
スクリプト言語hnwには整数型、辞書型、集合型が存在する。 整数型のリテラルは$0$以上$10^6$以下の整数を十進数で表記したものである。 辞書型、集合型のリテラルは以下のEBNFに従う。
DICT = "{" , EXPR , ":" , EXPR , { "," , EXPR , ":" , EXPR } , "}" | "{}" ;
SET = "{" , EXPR , { "," , EXPR } , "}" ;
EXPR = DICT | SET | INTEGER ;
集合型か辞書型のリテラル$S$が与えられる。型を判定せよ。
制約
- $\lvert S \rvert \leq 50000$
- 入力に空白は含まれない
解法
このような構文解析はEXPRを受け取り、型を判定するオラクルが存在すると仮定して考えると良いです。
まず、エイヤと関数だけ作ってしまいましょう。
enum HNW_TYPE {
DICT,
SET,
INTEGER,
UNDECIDED,
}
enum HNW_TYPE analize_expr (string s, ref int i) {
}
まず、INTEGERに関しては定義に再帰的なものが含まれていないため、これを処理します。
if ('0' <= s[i] && s[i] <= '9') {
while ('0' <= s[i] && s[i] <= '9') i++;
return HNW_TYPE.INTEGER;
}
別に数値をパースする必要はないので、読み飛ばしてしまいましょう。
DICT/SETのパースをしましょう。DICT/SETは必ず{から始まるので、ここを見つけるところからスタートです。
さらに、DICTのみ空なブラケットが許されるので、これは先に判定してしまいましょう。
if (s[i] == '{') {
i++;
if (s[i] == '}') { // 空のDICTのリテラル
i++;
return HNW_TYPE.DICT;
}
}
次に何らかのEXPRが来ますが、これは今作っている関数に丸投げします。
現時点でこの関数にEXPRを処理する能力はないですが、ばっちり処理してくれるということにします。
そのあとにはDICTであれば:が来て、SETであれば,か}が来ます。
auto res = HNW_TYPE.UNDECIDED;
bool end_of_expr = false;
while (true) {
// any EXPR
analize_expr(s, i);
switch (s[i]) {
case ':': // DICT
i++;
analize_expr(s, i);
res = HNW_TYPE.DICT;
break;
case ',': // SET
res = HNW_TYPE.SET;
break;
case '}': // SET
res = HNW_TYPE.SET;
break;
default:
assert(0);
}
// 後ろの余計なものを処理
switch (s[i]) {
case ',':
i++;
break;
case '}':
i++;
end_of_expr = true;
break;
default:
assert(0);
}
if (end_of_expr) break;
}
これでよさそうです。今までのものをつなげましょう。
実装
enum HNW_TYPE {
DICT,
SET,
INTEGER,
UNDECIDED,
}
enum HNW_TYPE analize_expr (string s, ref int i) {
if ('0' <= s[i] && s[i] <= '9') {
while ('0' <= s[i] && s[i] <= '9') i++;
return HNW_TYPE.INTEGER;
}
if (s[i] == '{') {
i++;
if (s[i] == '}') { // 空のDICTのリテラル
i++;
return HNW_TYPE.DICT;
}
}
auto res = HNW_TYPE.UNDECIDED;
bool end_of_expr = false;
while (true) {
// any EXPR
analize_expr(s, i);
switch (s[i]) {
case ':': // DICT
i++;
analize_expr(s, i);
res = HNW_TYPE.DICT;
break;
case ',': // SET
res = HNW_TYPE.SET;
break;
case '}': // SET
res = HNW_TYPE.SET;
break;
default:
assert(0);
}
// 後ろの余計なものを処理
switch (s[i]) {
case ',':
i++;
break;
case '}':
i++;
end_of_expr = true;
break;
default:
assert(0);
}
if (end_of_expr) break;
}
return res;
}
後はこの関数に渡した返り値を見てやればよいです。
感想
$\lvert S \rvert \leq 50000$だったので、特に考えずに再帰処理することができました。 この問題に関しては判定するだけであって、かつ変な入力は与えられないのでそこまで大変ではありませんでした。 しかし、ガチ解析をするにはもう少しBNF等に対する専門知識が必要になると思います。(私は完全に雰囲気で解いています。)
この問題の公式解説が見つからなかったのですが、どこにあるか知っている人いませんか…？