2246:Matrix Chain Multiplication

keyword

構文解析　C++

概要

各行列のサイズが与えられる。このとき、(AB)Cなどの文字列が与えられるので、行列の積が計算できるときは要素の積の計算回数を出力する問題。
パースできれば答えを出すのは簡単。トークンがぴったり1文字分なので処理が簡単。

map<char, pair<int,int> > dict;
char line[1000];
int p;
pair<int,int> expression();
int64 ans;

pair<int,int> expression(){
    char c = line[p++];
    if('A' <= c && c<='Z') return dict[c];
    if(c == '('){
        pair<int,int> pre = expression(), post = expression();
        c = line[p++];
        if(c != ')') return MP(-1,-1);
        if(pre != MP(-1,-1)
            && post != MP(-1,-1)
            && pre.second == post.first){
            ans += pre.first * pre.second * post.second;
            return MP(pre.first, post.second);
        }
        return MP(-1,-1);
    }
}

int main(){
    for(char a='A'; a<='Z'; a++)
        dict[a] = MP(-1,-1);
    int i, n, x, y;
    char c;
    scanf("%d\n",&n);
    REP(i,n){
        scanf("%c %d %d\n",&c,&x,&y);
        dict[c] = MP(x,y);
    }
    while(scanf("%s\n",line)!=EOF){
        ans = 0;
        p = 0;
        if(expression() == MP(-1,-1)){
            puts("error");
        }
        else{
            printf("%lld\n",ans);
        }
    }
}