TreesAndBrackets [SRM731 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14836

括弧列で表現された2つの木t1とt2がある。
t1から葉を削除する操作を0回以上行って木t2に出来るか判定せよ。
木の子供の順序は変えられない。

前提知識

• 構文解析

解法

他の人の解法を見ると構文解析を使わずに解いているが、構文解析しよう。
関数fで構文解析して、木を生成している。
　
あとは、関数gでaからbを作れるか判定しよう。
判定は子供の順序が一定なおかげで、貪欲に等価に出来るか判定していくとよい。

struct Node { vector<Node*> c; };
Node* f(string t, int &i) {
    Node* res = new Node();
    i++;
    while (t[i] == '(') {
        res->c.push_back(f(t, i));
    }
    i++;
    return res;
}
int g(Node* a, Node* b) {
    if (a->c.size() < b->c.size()) return 0;

    int bi = 0;
    rep(ai, 0, a->c.size()) {
        if (bi == b->c.size()) return 1;
        int res = g(a->c[ai], b->c[bi]);
        if (res) bi++;
    }

    if (bi == b->c.size()) return 1;
    return 0;
}
struct TreesAndBrackets {
    string check(string t1, string t2) {
        t1 += "=";
        t2 += "=";
        int i = 0;
        auto a1 = f(t1, i);
        i = 0;
        auto a2 = f(t2, i);

        if (g(a1, a2)) return "Possible";
        else return "Impossible";
    }
};