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

题见: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在涉及到性能方面的运算时倍受排挤.