AOJ 2255 6/2(1+2)

9だと思います。

問題

6/2(1+2) | Aizu Online Judge

解法

今までのように返す値を単なるintみたいな感じにしても上手くいかないのでsetを返すようにする。式を分析するときはそれぞれのoperatorがどの順番で使われるのかをnext_permutationで調べていく(ただしもちろん構造的にoperatorを使う順序がおかしいこともあるのでその場合は無視する)。

typedef string::const_iterator State;

set<int> expression(State& begin);
set<int> factor(State& begin);

set<int> factor(State& begin) {
    if (*begin == '(') {
        begin++;
        auto ret = expression(begin);
        begin++;
        return ret;
    } else {
        set<int> ret;
        int tmp = 0;
        while (isdigit(*begin)) {
            tmp = 10*tmp + (*begin-'0');
            begin++;
        }
        ret.insert(tmp);
        return ret;
    }
}

set<int> expression(State& begin) {
    vector<set<int> > nums;
    vector<char> ops;
    nums.push_back(factor(begin));
    while (*begin == '+' || *begin == '-' || *begin == '*' || *begin == '/') {
        ops.push_back(*begin);
        begin++;
        nums.push_back(factor(begin));
    }
    int n = ops.size();
    vector<int> perm(n);
    for (int i = 0; i < n; i++) perm[i] = i;
    set<int> ret;
    do {
        vector<set<int> > buff = nums;
        bool ng = false;
        for (int i = 0; i < n; i++) {
            int L = perm[i], R = L+1;
            char op = ops[perm[i]];
            while (L >= 0 && buff[L].size() == 0) {
                L--;
            }
            if (L < 0) {
                ng = true;
                break;
            }
            set<int> to;
            for (auto el1 : buff[L]) {
                for (auto el2 : buff[R]) {
                    if (op == '+') to.insert(el1+el2);
                    if (op == '-') to.insert(el1-el2);
                    if (op == '*') to.insert(el1*el2);
                    if (op == '/' && el2 != 0) to.insert(el1/el2);
                }
            }
            buff[L] = to;
            buff[R].clear();
        }
        if (!ng) {
            for (int el : buff[0]) {
                ret.insert(el);
            }
        }
    } while (next_permutation(perm.begin(), perm.end()));
    return ret;
}

void solve(const string& s) {
    State begin = s.begin();
    auto ans = expression(begin);
    cout << ans.size() << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    while (cin >> s) {
        if (s == "#") break;
        solve(s);
    }
    return 0;
}