CSP 202303-3 LDAP

黎 浩然/ 17 8 月, 2023/ 算法/ALGORITHMS/ 0 comments

C++：100/100

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

unordered_map<int, unordered_map<int, int>> attrs;

vector<int> base_expr(const string& exp, int start, int end) {
    char op;
    bool matched;
    int num1, num2;
    vector<int> res;
    stringstream ss(exp.substr(start, end - start));

    ss >> num1 >> op >> num2;
    for (pair<const int, unordered_map<int, int>> & attr : attrs)
        if (attr.second.find(num1) != attr.second.end()) {
            matched = attr.second[num1] == num2;
            if ((op == ':' && matched) || (op == '~' && (!matched)))
                res.push_back(attr.first);
        }
    sort(res.begin(), res.end());
    return res;
}

vector<int> expr(string exp, int start, int end, vector<int> quo) { // NOLINT(misc-no-recursion)
    if (exp[start] == '&' || exp[start] == '|') {
        vector<int> res1 = expr(exp, start + 2, quo[start + 1], quo);
        vector<int> res2 = expr(exp, quo[start + 1] + 2, quo[quo[start + 1] + 1], quo);
        vector<int> res;
        if (exp[start] == '&')
            set_intersection(res1.begin(), res1.end(), res2.begin(), res2.end(), back_inserter(res));
        else
            set_union(res1.begin(), res1.end(), res2.begin(), res2.end(), back_inserter(res));
        return res;
    }
    else if (exp[start] == '(')
        return expr(exp, start + 1, end - 1, quo);
    return base_expr(exp, start, end);
}

vector<int> expr_quo(const string& exp) {
    vector<int> quotation(exp.length());
    stack<int> stack;
    int idx;
    for (int i = 0; i < exp.length(); ++i)
        if (exp[i] == '(')
            stack.push(i);
        else if (exp[i] == ')') {
            idx = stack.top(), stack.pop();
            quotation[i] = idx, quotation[idx] = i;
        }
    return quotation;
}

int main() {
    int n, m, dn, key, val;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> dn >> m;
        unordered_map<int, int> attr;
        for (int j = 0; j < m; ++j) {
            cin >> key >> val;
            attr[key] = val;
        }
        attrs[dn] = attr;
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        string expression;
        cin >> expression;
        vector<int> res = expr(expression, 0, (int)expression.length(), expr_quo(expression));
        for (int re : res)
            cout << re << " ";
        cout << endl;
    }
    return 0;
}