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

import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.Stack;

public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
        int n = Integer.parseInt(sc.nextLine());
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(sc.nextLine());
        }
        List<String> newList = new ArrayList<>();
        String matchStr = sc.nextLine();
        Stack<Character> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < matchStr.length(); i++) {
            if (!stack.isEmpty() && matchStr.charAt(i) == ')') {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty() && stack.peek() != '(') {
                    sb.insert(0, stack.pop());
                }
                //依据题意，每个括号只有2个元素，所以后续直接处理两个元素即可。否则用while再判断多个元素会超时
                String str = sb.toString();
                int newInt = newList.size();
                char[] replaceChars = str.substring(0, 2).toCharArray();
                String a1 = "", a2 = "";
                if (Character.isLetter(replaceChars[0])) {
                    a1 = list.get(replaceChars[0] - 'A');
                } else {
                    a1 = newList.get(Integer.parseInt(replaceChars[0] + ""));
                }
                if (Character.isLetter(replaceChars[1])) {
                    a2 = list.get(replaceChars[1] - 'A');
                } else {
                    a2 = newList.get(Integer.parseInt(replaceChars[1] + ""));
                }
                str = newInt + str.substring(2, str.length());
                String[] a1Str = a1.split(" ");
                String[] a2Str = a2.split(" ");
                newList.add(a1Str[0] + " " + a2Str[1]);
                // 形成的新矩阵规律=A的行，B的列；计算次数=A的列*B的列*A的行
                sum += Integer.parseInt(a1Str[1]) * Integer.parseInt(a2Str[1]) *
                       Integer.parseInt(a1Str[0]);

                stack.pop();
                stack.push(str.charAt(0));
            } else {
                stack.push(matchStr.charAt(i));
            }
        }
        System.out.println(sum);
    }
}

}