矩阵链乘（Matrix Chain Multiplication）-蒲公英云

矩阵链乘（Matrix Chain Multiplication）

题目描述

假设你必须评估一种表达形如 ABCDE，其中 A,B,C,D,E是矩阵。既然矩阵乘法是关联的，那么乘法的顺序是任意的。然而，链乘的元素数量必须由你选择的赋值顺序决定。
例如，A，B，C分别是 50 * 10 ，10 * 20 和 20 * 5 的矩阵。现在有两种方案计算 A * B * C ,即（A * B) * C 和 A*(B * C)。
第一个要进行15000次基本乘法，而第二个只进行3500次。
你的任务就是写出一个程序判定以给定的方式相乘需要多少次基本乘法计算。

输入格式

输入包含两个部分：矩阵和表达式。
输入文件的第一行包含了一个整数 n(1 ≤ n ≤ 26), 代表矩阵的个数。接下来的n行每一行都包含了一个大写字母，说明矩阵的名称，以及两个整数，说明行与列的个数。
第二个部分严格遵守以下的语法：
SecondPart = Line { Line }
Line = Expression
Expression = Matrix | “(” Expression Expression “)”
Matrix = “A” | “B” | “C” | … | “X” | “Y” | “Z”

输出格式

对于每一个表达式，如果乘法无法进行就输出 “ error “。否则就输出一行包含计算所需的乘法次数。

输入输出样例

输入

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

输出

0
0
error
10000
error
3500
15000
40500
47500
15125
#include<cstdio>
#include<stack>
#include<iostream>
#include<string>
using namespace std;
struct matrix
{ 
    int a,b;
    matrix(int a=0,int b=0):a(a),b(b){ }
}m[26];
stack<matrix> s;
int main()
{ 
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    { 
      string name;
      cin>>name;
      int k=name[0]-'A';
      cin>>m[k].a>>m[k].b;
    }
    string expr;
    while(cin>>expr)
    { 
      int len=expr.length();
      bool error=false;
      int ans=0;
      for(int i=0;i<len;i++)
      { 
            if(isalpha(expr[i]))
            { 
            s.push(m[expr[i]-'A']);
            }
            else if(expr[i]==')')
            { 
            matrix m2=s.top();
            s.pop();
            matrix m1=s.top();
            s.pop();
            if(m1.b!=m2.a)
            { 
                 error=true;
                    break;
            }
            ans+=m1.a*m1.b*m2.b;
            s.push(matrix(m1.a,m2.b)); 
            }
      }
      if(error)
      { 
            printf("error\n");
      }
      else
      { 
            printf("%d\n",ans);
      }
    }
    return 0;
}