ICPC練習会2011 Problem.D 6÷2(1+2)

演算子の優先順位がわからないときに、何通り答えがあるかを求める問題。
頑張ってDPを使って解いてみた。
CYK法(Cocke-Younger-Kasami法:文脈自由文法が与えられたときに構文木を導出するアルゴリズム)みたいな手法。
授業で扱ったような気がするけど、実際実装しようとなると、添字の範囲とかが混乱する・・・。

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

typedef set<int> si;

string str;
unsigned int p;

si count() {
    si num[15][15];
    vector<char> op;

    int c = 0;
    while(p<str.size()) {
        char ch = str[p++];
        if(ch==')') break;
        else if(ch=='(') {
            num[c][0] = count();
            c++;
        } else if('0'<=ch && ch<='9') {
            int n = ch - '0';
            while(p<str.size() && '0'<=str[p] && str[p]<='9') {
                n = n*10 + str[p++]-'0';
            }
            num[c][0].insert(n);
            c++;
        } else {
            op.push_back(ch);
        }
    }

    for(int j=1;j<c;j++) {
        for(int i=0;i+j<c;i++) {
            si &s = num[i][j];
            for(int k=0;k<j;k++) {
                si &a = num[i][k];
                si &b = num[i+k+1][j-k-1];
                char ch = op[i+k];
                for(si::iterator ai=a.begin(); ai!=a.end(); ai++) {
                    for(si::iterator bi=b.begin(); bi!=b.end(); bi++) {
                        if(ch=='+') s.insert(*ai + *bi);
                        if(ch=='-') s.insert(*ai - *bi);
                        if(ch=='*') s.insert(*ai * *bi);
                        if(ch=='/' && *bi!=0) s.insert(div(*ai,*bi).quot);
                    }
                }
            }
        }
    }

    return num[0][c-1];
}

int main() {
    while(true) {
        cin >> str;
        if(str=="#") break;

        p = 0;
        cout << count().size() << endl;
    }
    return 0;
}