[UVA]UVA – 442 Matrix Chain Multiplication – 矩阵链乘

题目地址:

https://cn.vjudge.net/problem/UVA-442

题目描述:

(爱词霸翻译)

Background
背景

Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.
假设你要评价一个表达式A×B×C×D×E,A,B,C,D和E是矩阵。矩阵乘法是联想,其中乘法的执行顺序是任意的。然而,基本的乘法次数取决于你选择的求值顺序。

For example, let A be a 50*10 matrix, B a 10*20 matrix and C a 20*5 matrix. There are two different strategies to compute A*B*C, namely (A*B)*C and A*(B*C).
例如,设A是一个50×10矩阵,B是一个10×20的矩阵,C是 20×5的矩阵。有计算A×B×C的两种不同的策略,即(A×B)×C 和 A ×(B×C)。

The first one takes 15000 elementary multiplications, but the second one only 3500.
第一个需要15000个基本的乘法,但第二个只有3500。

Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.
你的任务是写一个程序来确定基本乘法对于一个给定的评价策略所需要的数量。

The Input
输入

Input consists of two parts: a list of matrices and a list of expressions. The first line of the input file contains one integer n (1 ≤ n ≤ 26), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.
输入由两部分组成:一个矩阵列表和列表的表达式。输入文件的第一行包含一个整数N(1≤N≤26),代表第一部分矩阵的数。接下来的N行每行包含一个大写字母,指定矩阵的名字,和两个整数,指定矩阵的行数和列数。

The second part of the input file strictly adheres to the following syntax (given in EBNF):
输入文件的第二部分严格遵守下列语法(在EBNF):

SecondPart = Line { Line }<EOF>
Line = Expression<CR>
Expression = Matrix | “(” Expression Expression “)”
Matrix = “A” | “B” | “C” | … | “X” | “Y” | “Z”

The Output
输出

For each expression found in the second part of the input file, print one line containing the word ‘error’ if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.
每个表达发现在输入文件的第二部分,打印一行字’错误’如果表达式评估导致由于非矩阵匹配错误。否则,打印一行含有小学乘法需要计算表达式的括号中指定数量的方式。

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
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

Sample Output
输出示例

0
0
0
error
10000
error
3500
15000
40500
47500
15125


我的分析

我本以为本题可以轻松解决,因为思路挺简单。然而对数据的存储,我还是缺少灵性。一开始我考虑到通过用字符‘A’的ASCII 码为65这个条件,通过读取字符直接减去65取到下标0进行赋值,故我一开始设的栈的数据类型为字符。然而写到后面,在存储计算结果(两个矩阵相乘后得到的新的结果)时,我不知道用什么字符去存比较好。因为数据一旦大起来,那些字符是完全不够用的。虽然我有想过用结构体,但之前的某些题目得到的教训是,结构体太过笨重,很可能拖满程序速度。

我忍不住翻开紫书看讲解,发现本题确实用结构体会好一些。将结构体存入栈中,若是得到新的结果,也可以临时生成一个结构体对象放进栈中,供之后使用。这确实是比较好的做法。

代码