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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //命名矩阵
        char start = 'A';
        //记录行索引输入和退出的行数
        int index = 0;
        int length = 0;
        //存放矩阵对应的坐标值
        Map<Character, String> map = new HashMap();
        while (in.hasNextLine()) {
            String target = in.nextLine();
            //todo start
            if (index == 0) {
                length = Integer.parseInt(target) + 2;
            }
            //存储矩阵数据
            if (index != 0 && index != length - 1) {
                map.put((char) (start + index - 1), target);
            }
            index++;

            if (index == length) {
                //todo
                int res = 0;
                //指定的矩阵计算规则
                String rule = target;
                Stack<Character> stack = new Stack<>();
                Stack<Character> eleStack = new Stack<>();
                eleStack.push('@');
                for (int i = 0; i < rule.length() && !eleStack.isEmpty(); i++) {
                    char c = rule.charAt(i);
                    if (c == '(') {
                        stack.push(c);
                    } else if (c == ')') {
                        stack.pop();
                        char other = eleStack.pop();
                        Character one = eleStack.pop();

                        //计算one矩阵和other矩阵的计算次数count
                        //do 只有栈可以保证规则下相乘的顺序
                        String otherR = map.get(other);
                        String oneR = map.get(one);
                        /**
                         * 该算法导致矩阵计算存在计算后other和one行列不分的情况。需要按照括号匹配程度去*/
                        Integer x0 = Integer.valueOf(oneR.split(" ")[0]);
                        Integer y0 = Integer.valueOf(oneR.split(" ")[1]);
                        Integer x1 = Integer.valueOf(otherR.split(" ")[0]);
                        Integer y1 = Integer.valueOf(otherR.split(" ")[1]);
                        Integer hang = 0;
                        Integer lie = 0;
                        Integer same = 0;
                        if (x0.equals(y1)) {
                            hang = x1;
                            lie = y0;
                            same = x0;
                        }
                        if (x1.equals(y0)) {
                            hang = x0;
                            lie = y1;
                            same = x1;
                        }
                        res += hang * same * lie;
                        other = (char) (other + one);
                        map.put(other, hang + " " + lie);
                        eleStack.push(other);

                    } else {
                        eleStack.push(c);
                    }
                }
                System.out.println(res);
                break;
            }
            if ("".equals(target)) {
                break;
            }
        }
        in.close();
    }
}