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

import java.util.*;

public class Main {
    static class Matrix {
        String name;
        int rows;
        int cols;

        public Matrix(String name, int rows, int cols) {
            this.name = name;
            this.rows = rows;
            this.cols = cols;
        }

    }

    //用来装所有矩阵包括中间计算的过程矩阵，例如A*B*C  先算A*B 再算AB*C 所以会把AB ABC 这两个矩阵都装进去
    static List<Matrix> matrixList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();
        //接受数据
        int n = sc.nextInt();
        byte a = 'A';
        for (int i = 0; i < n; i++) {
            Matrix matrix = new Matrix(new String(new byte[] {a}), sc.nextInt(),
                                       sc.nextInt());
            a++;
            matrixList.add(matrix);
        }

        int result = 0;
        // 由于上个sc调用的nextInt 所以在这后面会多一个\n.
        // 如果不想多用一个sc.nextLine接受这多余的一个\n的话可以考虑用String string = sc.next();
        sc.nextLine();
        String string = sc.nextLine();
        String[] split = string.split("");
        for (int i = 0; i < split.length; i++) {
            String temp = split[i];
            if (temp.equals(")")) {
                //这里的清空操作必不可少，要么放前面要么放后面。
                list.clear();
                //弹出在最后一个"("前的所有元素
                while (!stack.lastElement().equals("(")) {
                    list.add(stack.pop());
                }
                String[] strings = new String[list.size()];
                for (int j = 0; j < list.size(); j++) {
                    strings[j] = list.get(j);
                }
                //由于栈弹出的顺序与计算顺序相反，所有反向遍历数组
                String temp1 = strings[strings.length - 1];
                for (int j = strings.length - 2; j >= 0; j--) {
                    String temp2 = strings[j];

                    //通过名字获得对应的矩阵对象
                    Matrix m1 = getMatrixByName(temp1);
                    Matrix m2 = getMatrixByName(temp2);
                    // 两个矩阵[x,y][y,z]相乘 最后的矩阵会是[x,z]所以总共有x*z个元素
                    // 而（i,j）元素是第一个矩阵的i行的y个元素依次乘第二个矩阵的j列的y个元素
                    // 所以最后的总乘算次数 是 x*y*z
                    result += m1.rows * m1.cols * m2.cols;

                    // A*B = AB  把AB作为新的矩阵存入matrixList,以便查询和使用
                    temp1 = temp1 + temp2;
                    matrixList.add(new Matrix(temp1, m1.rows, m2.cols));
                }
                // 弹出"("
                stack.pop();
                // 将新的结果矩阵的名字压入栈
                stack.push(temp1);
            } else {
                //如果不是")"则直接入栈
                stack.push(temp);
            }
        }
        // 最后的栈中只会有一个元素
        System.out.println(result);
    }

    /**
     * 通过名字在matrixList中查找对应的矩阵对象
     * @param name
     * @return
     */
    public static Matrix getMatrixByName(String name) {
        for (int i = 0; i < matrixList.size(); i++) {
            Matrix temp = matrixList.get(i);
            if (temp.name.equals(name)) {
                return temp;
            }
        }
        return null;
    }
}