矩阵乘法:计算任给矩阵表达式(乘法)执行的元乘积次数

rappy

题见:http://acm.zju.edu.cn/show_problem.php?pid=1094
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
附代码如下:
public long calculateElementMul(Map<String, int[]> map, String exp)throws DataFormatException {Stack<String> expStack;long times = 0;// ０代表括号，１代表一个矩阵，２代表两个矩阵相乘int k = 0;// 0代表括号中没有矩阵,1代表括号中只有一个矩阵,类推int t = 0;int left[] = new int[2];int right[] = new int[2];int index = 0;while (exp.length() > 1) {expStack = new Stack<String>();for (int i = 0; i < exp.length(); i++) {String str = exp.substring(i, i + 1);expStack.push(str);if (str.matches("[A-Z]|([0-9])*")) {k++;t++;} else if (str.matches("\\(|\\)")) {if (str.equals(")") && t == 1) {expStack.pop();String temp = expStack.pop();expStack.pop();try {String pre = expStack.pop();if (pre.matches("[A-Z]|([0-9])*")) {t++;k++;}expStack.push(pre);} catch (EmptyStackException ese) {}expStack.push(temp);} else {t = 0;k = 0;}}if (k == 2) {right = (int[]) map.get(expStack.pop());left = (int[]) map.get(expStack.pop());if (left[1] != right[0])throw new DataFormatException("error");map.put(Integer.toString(index), new int[] { left[0],right[1] });times += left[0] * left[1] * right[1];expStack.push(Integer.toString(index));index++;k--;t--;}}StringBuffer sb = new StringBuffer();for (String string : expStack) {sb.append(string);}exp = sb.toString();}return times;}
代码只提供核心实现部分.
输入输出控制未提供.
可惜那边没有提供java的解答方式.
看来java在涉及到性能方面的运算时倍受排挤.