uva442

这题说的是给了一个矩阵连乘的表达式，要求判断是否合法，括符是合法的就是表达式可能不合法 ， 不合法的 输出 error 合法的输出 多少次运算， 采用递归 找到对应的区间递归下去 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
char str[1000005];
P R[30];
ll ans;
int idx(char A){
   return A-'A';
 }
void dfs(int Lc, int Rc, P &E)
{
     if(ans==-1) return ;
    E.first=E.second=-1;
    if(Lc>=Rc){
        if(Lc==Rc&&str[Lc]!='('&&str[Lc]!=')'){
             E=R[idx(str[Lc])];
        }
        return ;
    }
    P F;
    bool f=false;
    for(int i=Lc; i<=Rc; ++i){
        if(str[i]=='('){
            P W;
            int num=1,j=i;
            while(num!=0){
                j++;
                 if(str[j]=='(') num++;
                 else if(str[j]==')') num--;

            }
            dfs(i+1,j-1,W);
            if(ans==-1) return ;
            i = j ;
            if(f==false){
                 f=true;
                 F=W;
            }else{
                if( F.second != W.first ){
                     ans=-1; return ;
                }
                ans+= F.first*F.second*W.second;
                F.second=W.second;
            }

        }else{
          int loc=str[i]-'A';
          if(f==false){
              f=true;
              F=R[loc];
          }else{
            if(F.second!=R[loc].first){
                 ans=-1; return ;
            }
            ans+= F.first*F.second*R[loc].second;
            F.second=R[loc].second;
          }

        }

    }
    E=F;
}
int main()
{
     int n;
     char st[5];
     scanf("%d",&n);
     for(int i=0; i<n; ++i){
        scanf("%s",st);
        scanf("%lld%lld",&R[st[0]-'A'].first,&R[st[0]-'A'].second);
     }
     while(scanf("%s",str)==1){
         int len= strlen(str);
         ans=0;
         P f;
         dfs(0,len-1,f);
         if(ans==-1){
             printf("error
");
         }  else printf("%lld
",ans);
     }
    return 0;
}