矩阵链乘（Matrix Chain Multiplication）

拼搏现实的明天。 2022-12-01 01:21 122阅读 0赞

#### 题目描述 ####

假设你必须评估一种表达形如 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;
    }