首页 > 代码库 > uva442

uva442

2024-07-31 22:13:49   211人阅读

这题说的是给了一个矩阵连乘的表达式，要求判断是否合法，括符是合法的就是表达式可能不合法 ， 不合法的 输出 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\n");         }  else printf("%lld\n",ans);     }    return 0;}
View Code

 

uva442


联系
我们