COJ 0016 20603矩阵链乘

传送门：http://oj.cnuschool.org.cn/oj/home/solution.htm?solutionID=35454

20603矩阵链乘

难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B

试题描述

输入n个矩阵的维度和一些矩阵链乘的表达式，输出乘法的次数。如果乘法无法进行，输出error。假定A是m*n矩阵，B是n*p矩阵，则乘法的次数为m*n*p。如果矩阵A的列数不等于矩阵B的行数，则这两个矩阵无法进行乘法运算。例如：A是50*10的，B是10*20的，C是20*5的，则 A（BC）的乘法次数为10*20*5（BC的乘法次数）+50*10*5（A（BC）的乘法次数）=3500. 此题数据有误，2015-4-25已修正。

输入

第一行包括一个正整数n，表示共有n个矩阵参与运算。 接下来的n行，每行包括三部分，第一部分是矩阵的名字（一个大写字母），第二部分和第三部分各是一个正整数，分别表示该矩阵的行数和列数，这三部分之间有一个空格分隔。 最后一行包括一个矩阵运算的合法字符串（只包括小括号和上述矩阵的名称）

输出

按题目描述中的要求输出

输入示例

3 A 50 10 B 10 20 C 20 5 A(BC)

输出示例

3500

其他说明

数据范围：表达式的长度不超过100个字符。所有数据运算不会超过int32范围。

栈处理简单表达式。

 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<cstring>
 #include<stack>
 using namespace std;
 const int maxn=+;
 int n;
 struct Matrix{
     int a,b;
 }M[maxn];
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
     while(isdigit(ch)) x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;} if(x<) putchar('-'),x=-x;
     int len=,buf[]; while(x) buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
 }
 int solve(Matrix& a,Matrix b){
     int ans=-;
     if(a.b==b.a){ans=a.a*b.b*b.a;a.b=b.b;}
     return ans;
 }
 void init(){
     n=read();
     char ch;
     for(int i=;i<=n;i++){
         do ch=getchar(); while(isalpha(ch)!=);
         int id=ch-'A';
         M[id].a=read();
         //write(M[id].a); putchar('\n');
         M[id].b=read();
         //write(M[id].b); putchar('\n');
     }
     return;
 }
 stack<Matrix> S;
 void work(){
     int ans=;
     char s[maxn];scanf("%s",s);
     int len=strlen(s);
     for(int i=;i<len;i++){
         if(isalpha(s[i])) S.push(M[s[i]-'A']);
         else if(s[i]==')'){
             Matrix t2=S.top();S.pop();
             Matrix t1=S.top();S.pop();
             int t=solve(t1,t2);
             if(t<){puts("error");return;}
             ans+=t;S.push(t1);
         }
     }
     Matrix t2=S.top();S.pop();
     Matrix t1=S.top();S.pop();
     int t=solve(t1,t2);
     if(t<){puts("error");return;}
     ans+=t;
     write(ans);
     return;
 }
 void print(){
     return;
 }
 int main(){
     init();work();print();return ;

 }