構文解析練習第三弾。AOJ-ICPC 350 点。

問題概要

(5-3*4)*(0-2+1)

のような以下の BNF で定義される計算式が与えられる:

<expr> ::= ( <expr> ) | <number> | <expr> <op> <expr>
<op> ::= + | - | *

ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優先順位を定めても良い:

演算子は必ず左結合である。 (同じ優先順位の演算子は必ず数式の左側から計算する。)
異なる演算子が同じ優先順位であってもよい。

優先順位を調節して、計算結果が最大になるようにせよ。

解法

通常の再帰降下パーサは

expr: 「+」「-」を処理しつつ次の factor に
factor: 「*」「/」を処理しつつ次の term に
term: 「(」「)」や数値の処理

という再帰構造をしている。優先順位が高いものほど深くなっている。今回は「+」「-」「*」の優先順位が三段階ありうる。どの演算子がどの優先段階にあるかを 3³ = 27 通りすべて考えて求めてあげる。

実際の構文解析は、expr, expr2, expr3, term と関数を 4 つ用意してあげてもいいのだが、ここでは expr に深さ depth を引数として追加することで 1 つの関数で済ませてみた。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <climits>
#include <algorithm>
using namespace std;

set<char> aops[3]; // 演算子の優先順位

template<class T> struct Parser {
    // results
    int root;                       // vals[root] is the answer
    vector<T> vals;                 // value of each node
    vector<char> ops;               // operator of each node ('a' means leaf values)
    vector<int> left, right;        // the index of left-node, right-node
    vector<int> ids;                // the node-index of i-th value
    int ind = 0;
    
    void init() {
        vals.clear(); ops.clear(); left.clear(); right.clear(); ids.clear();
        ind = 0;
    }
    
    // generate nodes
    int newnode(char op, int lp, int rp, T val = 0) {
        ops.push_back(op); left.push_back(lp); right.push_back(rp);
        if (op == 'a') {
            vals.push_back(val);
            ids.push_back(ind++);
        }
        else {
            if (op == '+') vals.push_back(vals[lp] + vals[rp]);
            else if (op == '-') vals.push_back(vals[lp] - vals[rp]);
            else if (op == '*') vals.push_back(vals[lp] * vals[rp]);
            ids.push_back(-1);
        }
        return (int)vals.size() - 1;
    }
    
    // main solver
    T solve(const string &S) {
        int p = 0;
        root = expr(S, p);
        return vals[root];
    }
    
    // parser
    int expr(const string &S, int &p, int depth = 0) {
        if (depth < 3) {
            int lp = expr(S, p, depth + 1);
            while (p < (int)S.size() && aops[depth].count(S[p])) {
                char op = S[p]; ++p;
                int rp = expr(S, p, depth + 1);
                lp = newnode(op, lp, rp);
            }
            return lp;
        }
        else {
            if (S[p] == '(') {
                ++p;                    // skip '('
                int lp = expr(S, p, 0);
                ++p;                    // skip ')'
                return lp;
            }
            else {
                /* each process */
                long long val = 0;
                while (S[p] >= '0' && S[p] <= '9') {
                    val *= 10;
                    val += (int)(S[p] - '0');
                    ++p;
                }
                return newnode('a', -1, -1, val);
            }
        }
    }
};

int main() {
    string S; cin >> S;
    Parser<long long> ps;
    long long res = -LONG_MAX;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                for (int it = 0; it < 3; ++it) aops[it].clear();
                aops[i].insert('+');
                aops[j].insert('-');
                aops[k].insert('*');
                Parser<long long> ps;
                long long tmp = ps.solve(S);
                res = max(res, tmp);
            }
        }
    }
    cout << res << endl;
}

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

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

AOJ 2613 Unordered Operators (JAG 夏合宿 2013 day3-G) (350 点)

問題概要

解法