题目描述
假设你必须评估一种表达式，比如 A×B×C×D×E，其中 A、B、C、D、E是矩阵。既然矩阵乘法满足结合率，那么乘法的顺序是任意的。矩阵连乘的乘法次数由相乘的顺序决定。例如， A 、 B 、 C 分别是50×10、10×20和20×5的矩阵。 现在有两种方案计算 A × B × C ，即( A × B )× C 和 A×( B × C )。第1种要进行15000次乘法运算，而第2种只进行3500次乘法运算。
写程序，计算给定矩阵表达式需要进行多少次乘法运算。
写程序，计算给定矩阵表达式需要进行多少次乘法运算。
输入
输入包含矩阵和表达式两部分。
在第1部分，第1行包含一个整数n （1≤n ≤26），代表矩阵的个数；
接下来的n 行，每行都包含了一个大写字母来表示矩阵的名称，以及两个整数来表示矩阵的行数和列数。
第2部分是一个矩阵或矩阵表达式。
在第1部分，第1行包含一个整数n （1≤n ≤26），代表矩阵的个数；
接下来的n 行，每行都包含了一个大写字母来表示矩阵的名称，以及两个整数来表示矩阵的行数和列数。
第2部分是一个矩阵或矩阵表达式。
输出
对于每一个表达式，如果乘法无法进行，则输出“Error”，否则输出所需的乘法运算次数。
样例输入 Copy
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))
样例输出 Copy
0
0
0
error
10000
error
3500
15000
40500
47500
15125
提示
关于矩阵乘法，有以下3个问题必须先有了解。
1) 什么是矩阵相乘
如果第1个矩阵的列等于第2个矩阵的行，那么这两个矩阵是可乘的。如下图示：
2) 矩阵相乘后的结果是什么
两个矩阵相乘的结果矩阵，其行、列分别等于第 1 个矩阵的行、第 2 个矩阵的列。如果很多矩阵相乘呢?
多个矩阵相乘的结果矩阵，其行、列分别等于第 1 个矩阵的行、最后1个矩阵的列。而无论矩阵的计算次序如何，都不影响它们的结果矩阵。
3）两个矩阵相乘需要多少次乘法运算
例如，
和 
两个矩阵A3×2、B2×4相乘，结果为 C3×4，要怎么计算呢?
A矩阵第 1 行第 1 个数 × B 矩阵第 1 列第 1 个数: 1×2。
A矩阵第 1 行第 2 个数 × B 矩阵第 1 列第 2 个数: 2×3。
将两者相加并存放在 C矩阵第 1行第 1列:1×2+2×3。
A矩阵第 1 行第 1 个数 × B 阵第 2 列第 1 个数: 1x4。
A矩阵第 1 行第 2 个数 × B 阵第 2 列第 2 个数:2×6。
将两者相加并存放在 C 矩阵第 1 行第 2 列:1×4+2×6。
A矩阵第 1 行第 1 个数 × B 矩阵第 3 列第 1 个数:1×5。
A矩阵第 1 行第 2 个数 × B 阵第 3 列第 2 个数:2×9。
将两者相加并存放在 C 矩阵第 1 行第 3 列:1×5+2×9。
A矩阵第 1 行第 1 个数 × B 阵第 4 列第 1 个数:1×8。
A矩阵第 1行第 2个数 × B 阵第 4 列第 2个数: 2×10。
将两者相加并存放在 C 矩阵第 1 行第 4 列:1×8+2×10。
他行以此类推，计算结果如下图所示:
可以看出，结果矩阵中的每个元素都执行了两次乘法运算，那么在结果矩阵中有3×4=12个数，共需要要执行2×3×4=24 次乘法运算，两个矩阵A3×2、A2×4相乘执行乘法运算的次数为3×2×4,。Am×n、An×k相乘执行乘法运算的次数为 m×n×k。
1) 什么是矩阵相乘
如果第1个矩阵的列等于第2个矩阵的行，那么这两个矩阵是可乘的。如下图示：
2) 矩阵相乘后的结果是什么
两个矩阵相乘的结果矩阵，其行、列分别等于第 1 个矩阵的行、第 2 个矩阵的列。如果很多矩阵相乘呢?
多个矩阵相乘的结果矩阵，其行、列分别等于第 1 个矩阵的行、最后1个矩阵的列。而无论矩阵的计算次序如何，都不影响它们的结果矩阵。
3）两个矩阵相乘需要多少次乘法运算
例如，
和 两个矩阵A3×2、B2×4相乘，结果为 C3×4，要怎么计算呢?
A矩阵第 1 行第 1 个数 × B 矩阵第 1 列第 1 个数: 1×2。
A矩阵第 1 行第 2 个数 × B 矩阵第 1 列第 2 个数: 2×3。
将两者相加并存放在 C矩阵第 1行第 1列:1×2+2×3。
A矩阵第 1 行第 1 个数 × B 阵第 2 列第 1 个数: 1x4。
A矩阵第 1 行第 2 个数 × B 阵第 2 列第 2 个数:2×6。
将两者相加并存放在 C 矩阵第 1 行第 2 列:1×4+2×6。
A矩阵第 1 行第 1 个数 × B 矩阵第 3 列第 1 个数:1×5。
A矩阵第 1 行第 2 个数 × B 阵第 3 列第 2 个数:2×9。
将两者相加并存放在 C 矩阵第 1 行第 3 列:1×5+2×9。
A矩阵第 1 行第 1 个数 × B 阵第 4 列第 1 个数:1×8。
A矩阵第 1行第 2个数 × B 阵第 4 列第 2个数: 2×10。
将两者相加并存放在 C 矩阵第 1 行第 4 列:1×8+2×10。
他行以此类推，计算结果如下图所示:
可以看出，结果矩阵中的每个元素都执行了两次乘法运算，那么在结果矩阵中有3×4=12个数，共需要要执行2×3×4=24 次乘法运算，两个矩阵A3×2、A2×4相乘执行乘法运算的次数为3×2×4,。Am×n、An×k相乘执行乘法运算的次数为 m×n×k。