Problem1082--矩阵链乘

1082: 矩阵链乘

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 69  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

输入n个矩阵的维度和一些矩阵链乘表达式(表达式的括号都是匹配的,且每对括号中只包含两个矩阵),输出乘法的次数,如果乘法无法进行,输出error。
PS: 如果A是 nxm的矩阵,B是mxs的矩阵,则A乘B的乘法次数是n*m*s次。

Input

输入第一行代表输入矩阵的种类数 n (1<=n<=26)
以下n行每一行为一种矩阵的信息:
m row col , m是一个大写字母,代表矩阵种类,row是矩阵的行,col是矩阵的列。
接下来有多组测试用例,每一行输入字符串,代表矩阵链乘的表达式,以EOF结尾。
具体见样例。

Output

对于每一个矩阵链乘表达式,输出需要进行乘法的次数。如果遇到表达式不合法,输出"error"。

Sample Input

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
(AA)
(A(BC))
(D(E(F(G(HI)))))

Sample Output

0
error
3500
47500

Source/Category