假設你必須做A*B*C*D*E的運算,在這裡A,B,C,D,E都是矩陣(matrix)。由於矩陣相乘具有連結性(associative),所以相乘的順序可以是任意的。然而所需要的基本乘法數卻與不盡相同。
例如:A是個50*10的矩陣,B是個10*20的矩陣,C是個20*5的矩陣。那麼就有2種不同的表示式來求出A*B*C。分別是(A*B)*C和A*(B*C)。而其所需用到的基本乘法數前者為15000次,後者為3500次。
給你某一種矩陣相乘的表示式,你的任務是寫一個程式算出需要多少個基本乘法。
Input
輸入分為2部分。第一部份為矩陣的資料,第二部分為矩陣相乘的表示式。
第一列有一個整數n(1<= n <= 26),代表在輸入的第一部份有多少個矩陣。接下來的n列每列為一矩陣的資料。內容為1個大寫英文字母及2個整數,分別代表矩陣的名字,欄數(rows)及列數(columns)。
輸入的第二部分每列為一測試資料,內容為矩陣相乘的表示式。表示式嚴格的遵守以下的語法(以EBNF的形式)
SecondPart = Line { Line } <EOF> Line = Expression <CR> Expression = Matrix | "(" Expression Expression ")" Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
請參考Sample Input。
Output
對輸入第二部分的每組測試資料輸出一列。如果該表示式為不合法的矩陣相乘,則輸出error。否則請輸出此表示式所需的乘法次數。請參考Sample Output。
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