Mister雑記

競プロやります。

AOJ 2438 「YAML」

onlinejudge.u-aizu.ac.jp

問題

階層構造をもつオブジェクトを表現する、「YAML」という記法がある。

YAMLの形式に基づいたオブジェクトのデータが与えられるので、それをパースして指定されたプロパティを検索せよ。

今回与えられる入力は、BNF記法で以下のように表現できる。

yaml ::= mapping(0)
mapping(n) ::= mapping-item(n) | mapping-item(n) mapping(n)
mapping-item(n) ::= indent(n) key ':' ' ' string '\n'
                  | indent(n) key ':' '\n' mapping(m) (ただしm>n)

key    ::= [a-z0-9]+
string ::= [a-z0-9 ]+

indent(0)   ::= ""
indent(n+1) ::= ' ' indent(n)

制約

  • 検索するプロパティの深さ \leq 20
  • 入力に含まれる文字数 \leq 5 \times 10^4

考察

LL(1)なので気合で構文解析をする。ただ一気にやろうとすると面倒なので、大きく4段階に分けて実装した。

  1. 取得するプロパティをパース。
  2. 与えられた入力を(indent, key, body)の組へパース。
    • bodyを持たない(オブジェクトである)場合、bodyは空。
  3. 2で作ったデータをパースして、オブジェクトを構築する。
  4. プロパティを検索する。

この問題の核となるのはもちろん3である。


これは解説スライドから学んだことだが、パース関数の名前としてBNF記法で使われているものを使うと実装しやすい。構文解析では、脳死で与えられたBNF記法通りにパースするのが正解なのだろう。それが中々できないのだが。

解説スライドで参考資料に挙げられていたページがこちら

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// keyの列をパース
vector<string> get_keys() {
    string S;
    getline(cin, S);
    vector<string> ret;
    for (int i = 0; i < S.length(); ++i) {
        if (S[i] == '.') {
            ret.push_back("");
        } else {
            ret.back().push_back(S[i]);
        }
    }
    return ret;
}

// YAMLの各行の情報
struct Line {
    int n;  // spaceの数
    string key, body;
};
vector<Line> inputs;

// YAMLをLineの形式にパースしてinputsへ
void get_inputs() {
    string S;
    while (getline(cin, S)) {
        Line line;
        int itr = 0;

        // スペースを数える
        line.n = 0;
        while (S[itr] == ' ') {
            ++line.n;
            ++itr;
        }

        // keyを抽出
        while (S[itr] != ':') {
            line.key.push_back(S[itr]);
            ++itr;
        }
        itr += 2;  // :とspace

        while (itr < S.length()) {
            line.body.push_back(S[itr]);
            ++itr;
        }
        inputs.push_back(line);
    }
}


struct Obj {
    string key, body;
    vector<Obj> ch;
};

vector<Obj> mapping(int, int&);

Obj mapping_item(int n, int& itr) {
    Obj ret;
    ret.key = inputs[itr].key;
    ret.body = inputs[itr].body;
    ++itr;
    if (!ret.body.empty()) return ret;  // string

    ret.ch = mapping(inputs[itr].n, itr);  // object
    return ret;
}

vector<Obj> mapping(int n, int& itr) {
    vector<Obj> ret;
    while (itr < inputs.size() && inputs[itr].n == n) {
        ret.push_back(mapping_item(n, itr));
    }
    return ret;
}

int main() {
    vector<string> keys = get_keys();
    get_inputs();

    int itr = 0;
    vector<Obj> res = mapping(0, itr);

    string ans = "";
    for (auto k : keys) {
        bool found = false;
        for (auto obj : res) {
            if (obj.key == k) {
                // 1つ下へ潜る
                ans = obj.body;
                res = obj.ch;
                found = true;
                break;
            }
        }

        if (!found) {
            cout << "no such property" << endl;
            return 0;
        }
    }

    cout << (ans.empty() ? "object" : "string \"" + ans + "\"") << endl;
    return 0;
}

反省

  • 流石に実装に時間をかけすぎた。
  • 脳死で解析できるようになりたい。