けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1346 Miscalculation (ICPC アジア 2014 B) (200 点)

AOJ AOJ-ICPC AOJ-ICPC200点 ICPCアジア構文解析文字列構文解析:演算子の優先順位を設定する構文解析:再帰下降パーサ

アドホックにも実装できそうだけど、構文解析ライブラリで殴った！

問題へのリンク

問題概要

0 以上 9 以下の整数値に対して「+」「×」で連結して得られる長さ $N$ の文字列 $S$ が与えられる。たとえば以下のような文字列が与えられる。

1+2*3+4

また、Bob がこの式を見て計算して得た答えである整数 $B$ が与えられる。Bob がどのような考え方でこの答えを得たかの推測として、次の 2 つの方法を考えた。

「かけ算が先」ルール：かけ算を先に計算する
「左から右へ」ルール：演算子の優先順序に関係なく左から計算する

これらのルールを適用した結果に基づいて、以下の 4 種類の文字を出力せよ。

双方のルールで $B$ に一致するとき："U"
「かけ算が先」ルールのみで $B$ に一致するとき："M"
「左から右へ」ルールのみで $B$ に一致するとき："L"
双方のルールで $B$ に一致しないとき："I"

制約

$1 \le N \le 17$
$N$ は奇数
$S$ の先頭から奇数番目は整数 0〜9 を表す文字であり、偶数番目は '+', '*' のいずれかである
$0 \le B \lt 999999999$

考えたこと

手持ちの構文解析ライブラリは、演算子の優先順序を (タイ付きで) 設定できる作りにしている。

「かけ算が先」ルール：vector<vector> operator_mul = {{"*"}, {"+"}};
「左から右へ」ルール：vvector<vector> operator_left_right = {{"+", "*"}};

というように設定して、構文解析を実施した。

コード

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


// Parser (T must have constructor T(long long))
template<class T> struct Parser {
    /* basic settings */
    vector<vector<string>> OPERATORS;               // binary operator priority
    function<T(const string&, T, T)> OPERATION;     // binary operation

    /* optional settings */
    function<T(const string&, int&)> GET_LEAF;      // leaf parser
    vector<string> UNARY_OPERATORS;                 // unary operator (ex: "-", "log")
    function<T(const string&, T)> UNARY_OPERATION;  // unary operation
    const string OPERATOR_NUMBER = "num";
    
    /* results */
    string S;
    int root;                    // vals[root] is the answer
    vector<T> vals;              // value of each node
    vector<string> ops;          // operator of each node
    vector<int> left, right;     // the index of left-node, right-node
    vector<int> ids;             // the node-index of i-th value
    
    /* constructor */
    Parser() {}
    Parser(const vector<vector<string>> &operators,
           const function<T(const string&, T, T)> operation) {
        init(operators, operation);
    }
    Parser(const vector<vector<string>> &operators,
           const function<T(const string&, T, T)> operation,
           const function<T(const string&, int&)> get_leaf) {
        init(operators, operation, get_leaf);
    }
    Parser(const vector<vector<string>> &operators,
           const function<T(const string&, T, T)> operation,
           const function<T(const string&, int&)> get_leaf,
           const vector<string> &unary_operators,
           const function<T(const string &op, T)> unary_operation) {
        init(operators, operation, get_leaf, unary_operators, unary_operation);
    }
    void init(const vector<vector<string>> &operators,
              const function<T(const string&, T, T)> operation) {
        OPERATORS = operators, OPERATION = operation;
    }
    void init(const vector<vector<string>> &operators,
              const function<T(const string&, T, T)> operation,
              const function<T(const string&, int&)> get_leaf) {
        OPERATORS = operators, OPERATION = operation;
        GET_LEAF = get_leaf;
    }
    void init(const vector<vector<string>> &operators,
              const function<T(const string&, T, T)> operation,
              const function<T(const string&, int&)> get_leaf,
              const vector<string> &unary_operators,
              const function<T(const string &op, T)> unary_operation) {
        OPERATORS = operators, OPERATION = operation;
        GET_LEAF = get_leaf;
        UNARY_OPERATORS = unary_operators, UNARY_OPERATION = unary_operation;
    }
    void clear() {
        S = "";
        vals.clear(), ops.clear(), left.clear(), right.clear(), ids.clear();
    }
    
    /* node generator */
    // value
    int new_leaf(T val, int &id) {
        vals.push_back(val);
        ops.push_back(OPERATOR_NUMBER);
        left.push_back(-1);
        right.push_back(-1);
        ids.push_back(id++);
        return (int)vals.size() - 1;
    }
    // FUNC(lp)
    int new_node_with_left(T val, const string &op, int lp) {
        vals.push_back(val);
        ops.push_back(op);
        left.push_back(lp);
        right.push_back(-1);
        ids.push_back(-1);
        return (int)vals.size() - 1;
    }
    // (lp) op (rp)
    int new_node_with_left_right(const string &op, int lp, int rp) {
        vals.push_back(OPERATION(op, vals[lp], vals[rp]));
        ops.push_back(op);
        left.push_back(lp);
        right.push_back(rp);
        ids.push_back(-1);
        return (int)vals.size() - 1;
    }
    
    /* main parser */
    T parse(const string &str, bool default_parse_numeric = true) {
        clear();
        S = str;
        int p = 0, id = 0;
        root = parse(p, id, default_parse_numeric);
        return vals[root];
    }
    int parse(int &p, int &id, bool default_parse_numeric, int depth = 0) {
        assert(p >= 0 && p < (int)S.size());
        string op;
        if (depth < (int)OPERATORS.size()) {
            // recursive descent
            int lp = parse(p, id, default_parse_numeric, depth + 1);
            bool update = false;
            do {
                update = false;
                if (is_in_the_operators(p, op,
                                        OPERATORS[(int)OPERATORS.size() - depth - 1])) {
                    int rp = parse(p, id, default_parse_numeric, depth + 1);
                    lp = new_node_with_left_right(op, lp, rp);
                    update = true;
                }
            } while (p < (int)S.size() && update);
            return lp;
        }
        else if (S[p] == '(') {
            return get_bracket(p, id, default_parse_numeric);
        }
        else if (default_parse_numeric && (S[p] == '-' || isdigit(S[p]))) {
            return get_number(p, id);
        }
        else if (is_in_the_operators(p, op, UNARY_OPERATORS)) {
            return get_unary_operation(p, id, op, default_parse_numeric);
        }
        else {
            return new_leaf(GET_LEAF(S, p), id);
        }
    }
    bool is_the_operator(int &p, const string &op) {
        if (op != "" && S.substr(p, op.size()) == op) {
            p += op.size();
            return true;
        }
        return false;
    }
    bool is_in_the_operators(int &p, string &res_op, const vector<string> &ops) {
        for (const auto &op : ops) {
            if (is_the_operator(p, op)) {
                res_op = op;
                return true;
            }
        }
        return false;
    }
    int get_number(int &p, int &id) {
        long long val = 0, sign = 1;
        if (S[p] == '-') sign = -1, ++p;
        while (p < (int)S.size() && isdigit(S[p])) {
            val = val * 10 + (int)(S[p++] - '0');
        }
        return new_leaf(T(val * sign), id);
    }
    int get_bracket(int &p, int &id, bool default_parse_numeric) {
        ++p;  // skip "("
        int lp = parse(p, id, default_parse_numeric, 0);
        ++p;  // skip ")"
        return lp;
    }
    int get_unary_operation(int &p, int &id, const string &op,
                            bool default_parse_numeric) {
        int lp;
        if (S[p] == '(') lp = get_bracket(p, id, default_parse_numeric);
        else lp = parse(p, id, default_parse_numeric, (int)OPERATORS.size());
        return new_node_with_left(UNARY_OPERATION(op, vals[lp]), op, lp);
    }
    
    /* dump */
    void dump() {
        dump_rec(root);
    }
    void dump_rec(int v, string space = "") {
        cout << space << v << ": (" << ops[v] << ", " << vals[v]
             << ") -> left: " << left[v] << ", right: " << right[v] << endl;
        if (left[v] != -1) dump_rec(left[v], space + "  ");
        if (right[v] != -1) dump_rec(right[v], space + "  ");
    }
};


int main() {
    // multiplication-rool parser, left-to-right parser
    vector<vector<string>> operator_mul = {{"*"}, {"+"}};
    vector<vector<string>> operator_left_right = {{"+", "*"}};
    auto operation = [&](string op, long long a, long long b) -> long long {
        if (op == "+") return a + b;
        else return a * b;
    };
    Parser<long long> ps_mul(operator_mul, operation);
    Parser<long long> ps_left_right(operator_left_right, operation);
    
    string S;
    long long ans;
    cin >> S >> ans;
    
    bool mul = false, left_right = false;
    if (ps_mul.parse(S) == ans) mul = true;
    if (ps_left_right.parse(S) == ans) left_right = true;
    
    if (mul && left_right) cout << "U" << endl;
    else if (mul) cout << "M" << endl;
    else if (left_right) cout << "L" << endl;
    else cout << "I" << endl;
}