競プロ構文解析練習記録

Posted on 4 mins read

ICPCに向けた構文解析で解いた問題を記録しておきます。

基本的にLL(1)文法を再帰下降構文解析で処理しています。
draftcodeさんのgistやこちらの記事を参考に入門しました。　

AOJ 0109 スマート計算機(Smart Calculator)

一番基本の四則演算のパーサーです。

// 四則演算のParser
#include <bits/stdc++.h>
#define int long long
using namespace std;

// exp1 = exp2 [ ('+'|'-') exp2 ]*
// exp2 = exp3 [ ('*'|'/') exp3 ]*
// exp3 = '(' exp1 ')' | number

int exp1(const string& s, int& i);
int exp2(const string& s, int& i);
int exp3(const string& s, int& i);
int number(const string& s, int& i);
int exp1(const string& s, int& i) {
    int acc = exp2(s, i);
    while (1) {
        if (s[i] == '+')
            acc += exp2(s, ++i);
        else if (s[i] == '-')
            acc -= exp2(s, ++i);
        else
            return acc;
    }
}
int exp2(const string& s, int& i) {
    int acc = exp3(s, i);
    while (1) {
        if (s[i] == '*')
            acc *= exp3(s, ++i);
        else if (s[i] == '/')
            acc /= exp3(s, ++i);
        else
            return acc;
    }
}
int exp3(const string& s, int& i) {
    if (s[i] == '(') {
        int ret = exp1(s, ++i);
        assert(s[i] == ')');
        i++;
        return ret;
    }
    return number(s, i);
}
int number(const string& s, int& i) {
    int acc = 0;
    while (isdigit(s[i])) {
        acc = acc * 10 + (s[i++] - '0');
    }
    return acc;
}

void solve() {
    string s;
    cin >> s;
    int i = 0;
    cout << exp1(s, i) << endl;
    assert(s[i] == '=');
}
signed main() {
    int T;
    cin >> T;
    while (T--) solve();
}

AOJ 2584 壊れた暗号生成器(Broken Cipher Generator)

数値以外を返す問題の例です。
愚直な全探索も間に合うのですが、少し考えると全探索をする必要もないことがわかります。

#include<bits/stdc++.h>
#define int long long
using namespace std;

// exp1 = exp2 [ exp2 ]*
// exp2 = '[' exp1 ']' | exp3
// exp3 = '+'|'-' exp3

char prv(char c) {
    if (c == '?') return '?';
    return c == 'A' ? 'Z' : c - 1;
}
char nxt(char c) {
    if (c == '?') return '?';
    return c == 'Z' ? 'A' : c + 1;
}
string exp1(string& s, int& i);
string exp2(string& s, int& i);
char exp3(string& s, int& i);
string exp1(string& s, int& i) {
    string acc = exp2(s, i);
    while (i < s.size() && s[i] != ']') {
        acc += exp2(s, i);
    }
    return acc;
}
string exp2(string& s, int& i) {
    if (s[i] == '[') {
        string ret = exp1(s, ++i);
        assert(s[i] == ']');
        i++;
        reverse(ret.begin(), ret.end());
        return ret;
    }
    return ""s + exp3(s, i);
}
char exp3(string& s, int& i) {
    if (s[i] == '+') return nxt(exp3(s, ++i));
    if (s[i] == '-') return prv(exp3(s, ++i));
    return s[i++];
}
void solve() {
    string s; cin >> s;
    if (s == ".") exit(0);
    int i = 0;
    string t = exp1(s, i);
    for (auto& c : t) {
        if (c == '?') c = 'A';
    }
    cout << t << endl;
}
signed main() {
    while (1) solve();
}

AOJ 2570 Shipura

S<expr>という文法とterm<<termという文法を区別するために2つ先読みしないといけないパターン。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1e9 + 7;
int number(string& s, int & i) {
    int ret = 0;
    while (isdigit(s[i])) {
        ret = ret * 10 + (s[i++] - '0');
    }
    return ret;
}
int exp1(string& s, int & i);
int exp2(string& s, int & i);
int exp1(string& s, int & i) {
    int acc = exp2(s, i);
    while (i < s.size()) {
        if (s[i] == '>' && i + 2 < s.size() && s[i + 1] == '>' && s[i + 2] != '>') {
            i += 2;
            int rhs = exp2(s, i);
            acc = rhs < 32 ? acc / (1LL << rhs) : 0;
        } else break;
    }
    return acc;
}
int exp2(string& s, int & i) {
    if (s[i] == 'S') {
        assert(s[++i] == '<');
        int ret = exp1(s, ++i);
        assert(s[i++] == '>');
        return ret * ret % MOD;
    } else {
        return number(s, i);
    }
}
void solve() {
    string s;
    {
        string t;
        getline(cin, t);
        if (t == "#") exit(0);
        for (char c : t) {
            if (c != ' ') s.push_back(c);
        }
    }
    int i = 0;
    cout << exp1(s, i) << endl;
}

signed main() {
    while (1) solve();
}

AOJ 2613 Unordered Operators

演算子の優先順位を変更する面白い問題設定。
提出コードはこちら

AOJ 2255 6/2(1+2)

先程は演算子の種類によって優先順位を変更する問題でしたが、今回は種類にかかわらず順序を変更する問題。

各expressionが set<int> を返すように実装します。
練習中は演算子を区切る場所を全探索する(メモ化なしの)再帰でやりました(提出コード)が、構文木を作って区間DPするのが本筋っぽいのでその練習もしておきました。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int DUMMY = 1e13;
int op(int l, int r, char c) {
    if (l == DUMMY || r == DUMMY) return DUMMY;
    if (c == '+') return l + r;
    if (c == '-') return l - r;
    if (c == '*') return l * r;
    if (c == '/') return r == 0 ? DUMMY : l / r;
    assert(0);
}
bool is_op(char c) {
    return c == '+' || c =='-' || c == '*' || c == '/';
}

struct expr_t {
    int imd = -1;
    vector<expr_t> vals;
    vector<char> ops;
};
int number(string& s, int& i) {
    int acc = 0;
    while (isdigit(s[i])) {
        acc = acc * 10 + (s[i++] - '0');
    }
    return acc;
}
expr_t expr1(string& s, int& i);
expr_t expr2(string& s, int& i);

expr_t expr1(string& s, int& i) {
    expr_t ret;
    while (i < s.size() && s[i] != ')') {
        if (is_op(s[i])) {
            ret.ops.push_back(s[i++]);
        } else if (s[i] == '(') {
            ret.vals.push_back(expr1(s, ++i));
            i++;
        } else if (s[i] == ')') {
            i++;
            break;
        } else {
            ret.vals.push_back(expr2(s, i));
        }
    }
    return ret;
}
expr_t expr2(string& s, int& i) {
    return expr_t({number(s, i)});
}
set<int> calc(expr_t e) {
    if (e.imd != -1) {
        set<int> ret;
        ret.insert(e.imd);
        return ret;
    }
    assert(e.vals.size() == e.ops.size() + 1);
    int n = e.vals.size();
    vector<vector<set<int>>> dp(n, vector<set<int>>(n));
    function<set<int>(int, int)> dfs = [&](int i, int j) {
        set<int>& ret = dp[i][j];
        if (ret.size() != 0) return ret;
        if (i == j) return ret = calc(e.vals[i]);
        for (int k = i; k < j; k++) {
            set<int> ls = dfs(i, k);
            set<int> rs = dfs(k + 1, j);
            for (int l : ls) {
                for (int r : rs) {
                    ret.insert(op(l, r, e.ops[k]));
                }
            }
        }
        return ret;
    };
    return dfs(0, n - 1);
}
void solve() {
    string s; cin >> s;
    if (s == "#") exit(0);
    int i = 0;
    expr_t res = expr1(s, i);
    set<int> ret = calc(res);
    if (ret.count(DUMMY)) ret.erase(DUMMY);
    cout << ret.size() << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (1) solve();
}

Facebook Hacker Cup 2019 Qualification Round Mr. X

構文解析を自分で書かなくても、Pythonなどのインタプリタ言語のeval関数が使える場合もあります。

def solve():
    s = input()
    s1 = s.replace("x", "0").replace("X", "1")
    s2 = s.replace("X", "0").replace("x", "1")
    print(0 if eval(s1) == eval(s2) else 1)

if __name__ == "__main__":
    T = int(input())
    for t in range(1, T + 1):
        print("Case #{}: ".format(t), end="")
        solve()

AOJ 2704 スタンプラリー(Stamp Rally)

グラフ + 構文解析
結構むずかしい。

ワーシャルフロイドっぽいことをやりたくなるんですが、同じ頂点を2回通って得することもあるのでそんなに単純にはいかず、queueを使って工夫してDPします。
遷移を単純にして高速化するために状態数を増やしてチョムスキー標準形に直しておきます。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const string TBL = "a()[]+*";
map<pair<int, int>, int> trans;

void solve() {
    int n, m, s, t; cin >> n >> m >> s >> t;
    if (n == 0) exit(0);
    s--; t--;

    vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(9)));
    struct X { int i, j, c; };
    queue<X> q;
    while (m--) {
        int i, j; cin >> i >> j;
        i--; j--;
        char c_; cin >> c_;
        int c = TBL.find(c_);
        if (c == 6) c--;
        if (!dp[i][j][c]) dp[i][j][c] = true, q.push({i, j, c});
    }

    while (!q.empty()) {
        X x = q.front(); q.pop();
        for (int c = 0; c < 9; c++) {
            // (x.i, x.j), (x.j, k) -> (x.i, k)
            if (trans.count({x.c, c})) {
                int c2 = trans[{x.c, c}];
                for (int k = 0; k < n; k++) {
                    if (dp[x.j][k][c] && !dp[x.i][k][c2]) {
                        dp[x.i][k][c2] = true;
                        q.push({x.i, k, c2});
                    }
                }
            }
            // (k, x.i), (x.i, x.j) -> (k, x.j)
            if (trans.count({c, x.c})) {
                int c2 = trans[{c, x.c}];
                for (int k = 0; k < n; k++) {
                    if (dp[k][x.i][c] && !dp[k][x.j][c2]) {
                        dp[k][x.j][c2] = true;
                        q.push({k, x.j, c2});
                    }
                }
            }
        }
    }
    cout << (dp[s][t][0] ? "Yes" : "No") << endl;
}

signed main() {
    trans[{0, 5}] = 6;
    trans[{1, 0}] = 7;
    trans[{3, 0}] = 8;
    trans[{6, 0}] = 0;
    trans[{7, 2}] = 0;
    trans[{8, 4}] = 0;
    while (1) solve();
}