AOJ 1322 - ASCII Expression

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322

解法

今の左端と、上下の区間を持ちながら構文解析を書く。
base の位置は左から見ていって、初めて空白以外が現れた行としてよい。
分数表記のときに余計な space がたくさん入ることがあるので、base を見つける関数を切り分けてそこで左端の位置も更新しながらやればいいと思う。
ほかはいつもの構文解析と全く同じなので特に困ることはない。

最初問題を読んでなくて、有理数表現で計算してたら答えが合わなくて泣いてた。

ソースコード

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

constexpr int mod = 2011;

int add(int a, int b) {
    return (a + b) % mod;
}
int mul(int a, int b) {
    return a * b % mod;
}
int inv(int n) {
    int a = n, b = mod, u = 1, v = 0;
    while(b) {
        const int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    (u += mod) %= mod;
    return u;
}

int expr(int& x, int y1, int y2, vector<string> const&);
int term(int& x, int y1, int y2, vector<string> const&);
int factor(int& x, int y1, int y2, vector<string> const&);
int powexpr(int& x, int y1, int y2, vector<string> const& s);

int find_base(int& x, int y1, int y2, vector<string> const& s) {
    int res = -1;
    while(res == -1) {
        assert("[base] cannot find base" && x < (int)s[0].size());
        for(int y = y1; y < y2; ++y) {
            if(s[y][x] == '.') continue;
            res = y;
            break;
        }
        x += (res == -1);
    }
    return res;
}

int digit(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    assert(isdigit(s[base_y][x]));
    return s[base_y][x++] - '0';
}

int expr(int& x, int y1, int y2, vector<string> const& s) {
    // find base
    const int base_y = find_base(x, y1, y2, s);
    auto res = term(x, y1, y2, s);
    while(x + 1 < (int)s[0].size() && (s[base_y][x + 1] == '-' || s[base_y][x + 1] == '+')) {
        ++x; // space
        const char op = s[base_y][x];
        x += 2;
        const auto r = term(x, y1, y2, s);
        if(op == '+')      res = add(res, r);
        else if(op == '-') res = add(res, mod - r);
        else assert("[expr] invalid op" && false);
    }
    return res;
}

int term(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    auto res = factor(x, y1, y2, s);
    while(x + 1 < (int)s[0].size() && s[base_y][x + 1] == '*') {
        ++x; // space
        assert("[term] invalid op" && s[base_y][x] == '*');
        x += 2; // op
        res = mul(res, factor(x, y1, y2, s));
    }
    return res;
}

int factor(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    if(s[base_y][x] == '-' && s[base_y][x + 1] == '-') { // fraction
        int x1 = x + 1, x2 = x + 1;
        auto a = expr(x1, y1, base_y, s);
        auto b = expr(x2, base_y + 1, y2, s);
        x = max(x1, x2) + 1;
        return mul(a, inv(b));
    } else if(s[base_y][x] == '-') { // neg
        x += 2;
        return mul(factor(x, y1, y2, s), 2010);
    } else {
        return powexpr(x, y1, y2, s);
    }
}

// primary is in
int powexpr(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    int res = 1;
    if(s[base_y][x] == '(') {
        x += 2;
        res = expr(x, y1, y2, s);
        x += 2; // ".)"
    } else {
        assert(isdigit(s[base_y][x]));
        res = digit(x, base_y, base_y + 1, s);
    }
    if(base_y != 0 && isdigit(s[base_y - 1][x])) { // power
        int cnt = digit(x, base_y - 1, base_y, s);
        int t = 1;
        while(--cnt >= 0) {
            t = mul(t, res);
        }
        res = t;
    }
    return res;
}

int main() {
    int n;
    while(cin >> n, n) {
        vector<string> s(n);
        for(auto& ss : s) cin >> ss;
        int p = 0;
        cout << expr(p, 0, n, s) << endl;
    }
}

感想

ついに倒せたー。
個人的には Matrix Calculator のほうが虚無だった．