题解 | #矩阵乘法计算量估算#

import java.util.*;public class Main {private static int sum = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNextInt()){int n = in.nextInt();int a[][] = new int[n][2];for(int i = 0; i < n; i++){a[i][0] = in.nextInt();a[i][1] = in.nextInt();}String s = in.next();s = s.substring(1, s.length() - 1);calculate(a, s);System.out.println(sum);}}

public static int[] calculate (int a[][], String s) {
    ArrayList<Integer> list = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();

    for(int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if(ch >= 'A' && ch <= 'Z') {
            list.add(a[ch - 'A'][0]);
            list.add(a[ch - 'A'][1]);
        }
        //如果当前字符是小括号
        else if(ch=='(') {
            //移到小括号后一位字符
            int j = i + 1;
            //统计括号的数量
            int count = 1;
            while(count > 0) {
                //遇到右括号，括号数-1
                if(s.charAt(j) == ')') count--;
                //遇到左括号，括号数+1
                if(s.charAt(j) == '(') count++;
                j++;
            }
            //递归，解小括号中的表达式
            int b[] = calculate(a, s.substring(i + 1, j - 1));
            list.add(b[0]);
            list.add(b[1]);
            i = j - 1;
        }
    }

    for(int j = list.size() - 1; j >= 0; j -= 2) {
            stack.push(list.get(j));
            stack.push(list.get(j - 1));
    }
    int[] b = new int[2];
    while (true) {
        int x0 = stack.pop(), y0 = stack.pop();     // 矩阵尺寸x0*y0
        int x1 = stack.pop(), y1 = stack.pop();     // 矩阵尺寸x1*y1
        sum += x0 * y0 * y1;      // 两个矩阵的乘法次数为x0*y0*y1或x0*x1*y1（其中y0==x1）
        if (stack.empty()) {
            b = new int[]{x0, y1};
            break;
        }
        stack.push(y1);       // 把相乘后得到的矩阵列数入栈
        stack.push(x0);
    }
    return b;
}

}