矩阵链的乘积次数

题目描述:

假设你要计算一个表达式，比如A*B*C*D*E，其中A，B，C，D和E是矩阵。

然而，所需的乘法的数目取决于乘积的顺序。

例如，假设A是50*10矩阵，B是10*20矩阵，C是20*5矩阵。有两个计算A*B*C的不同策略，即（A*B）*C和A*（B*C）。

第一个需要15000次乘法，而第二个只需要3500次。

你的任务是编写一个程序，计算给定乘积顺序的所需乘法次数。

输入格式:

输入由两部分组成：矩阵列表和表达式列表。

输入的第一行包含一个整数n（1≤n≤26），表示有n个矩阵。

接下来的n行各包含一个大写字母，用于指定矩阵名，接着是两个整数，指定该矩阵的行数和列数。

输入的第二部分一个矩阵相乘的表达式，表达式中只包含小括号，以及第一部分给定的矩阵名。

输出格式:

一个整数，表示所需的乘积次数。

如果矩阵表达式运算失败，则输出”error“。

样例输入:

样例1：
2
A 50 10
B 30 20
(AB)

样例2：
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
(D(E(F(G(HI)))))

样例输出:

样例1：
error

样例2：
47500

提示:

每一对的矩阵相乘，都是放在括号中，请参看样例。

时间限制: 1000ms
空间限制: 256MB

---