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

如果机试没本地编译器根本没法调试啊，整个解题过程接受一点点找补，先把算法主体框架搭起来.
1、先将计算表达式转换为表达式树，AB \ A( \ )A \ )( 这几种情况两个符号之间插入''，如(A((B(C(DE)))(FG)))转换为(A((B(C(DE)))(FG)))，再将表达式树转换为后序遍历的结果；
2、计算乘法次数函数int cal(List<string> pl,int[][] h),遍历后续表达式，若是计算数，入栈，若是计算符，将栈顶两个元素出栈（两个元素代表两个矩阵如A,B），计算A、B矩阵的乘法运算次数（A1</string>A2B2），这里有个坑，出栈的元素的顺序与元素在后续表达式中的顺序想法，因此出栈时的计算应该为（B1B2*A2），计算出的中间结果怎么保存呢？在cal函数中声明一个中间结果矩阵数组t[maxn][2]；以int cur(初始值为0)为索引将中间结果放入t数组，再将cur转为字符串入栈stack.push(cur++)，因此在处理出栈元素时需要分类讨论，若出栈元素为字母如'A',则计算矩阵从输入矩阵中获取；若为数字（cur），则从中间结果矩阵中获取。最后将计算结果累加返回。
3、最后我这个代码还有个坑，postList集合因为是全局静变量，在每次计算完毕后需要清空，否则导致后续计算错误。

public static int maxn = 1000;
    public static int[] lch = new int[maxn], rch = new int[maxn];
    public static String[] op = new String[maxn];
    public static int nc = 0;
    public static List<String> postList = new ArrayList<>();

    public static int build(List<String> list, int x, int y) {
        int i, c1 = -1, p = 0;
        int u;
        if (y - x == 1) {
            u = ++nc;
            lch[u] = 0;
            rch[u] = 0;
            op[u] = list.get(x);
            return u;
        }
        for (i = x; i < y; i++) {
            switch (list.get(i)) {
                case "(":
                    p++;
                    break;
                case ")":
                    p--;
                    break;
                case "*":
                    if (p == 0) c1 = i;
                    break;
            }
        }
        if (c1 < 0) return build(list, x + 1, y - 1);
        u = ++nc;
        lch[u] = build(list, x, c1);
        rch[u] = build(list, c1 + 1, y);
        op[u] = list.get(c1);
        return u;
    }

    //(A(BC))
    public static void post(int u) {
        if (u == 0) return;
        post(lch[u]);
        post(rch[u]);
        if (op[u] != null) {
            postList.add(op[u]);
        }
    }

    public static int cal(List<String> pl, int[][] h) {
        Stack<String> stack = new Stack<>();
        int re = 0;
        int[][] t = new int[maxn][2];
        int cur = 0;
        for (String s : pl) {
            if (s.equals("*")) {
                String s1 = stack.pop();
                String s2 = stack.pop();
                char n1 = s1.charAt(0);
                char n2 = s2.charAt(0);
                int d1 = 0, d2 = 0, k1 = -1, k2 = -1;
                int temp = 0;
                if (n1 >= 'A' && n1 <= 'Z')
                    d1 = n1 - 'A';
                else k1 = Integer.parseInt(s1);
                if (n2 >= 'A' && n2 <= 'Z')
                    d2 = n2 - 'A';
                else k2 = Integer.parseInt(s2);
                if (k1 < 0 && k2 >= 0) {
                    temp = t[k2][0] * t[k2][1] * h[d1][1];
                    t[cur][0] = t[k2][0];
                    t[cur][1] = h[d1][1];
                }
                if (k1 < 0 && k2 < 0) {
                    temp = h[d2][0] * h[d2][1] * h[d1][1];
                    t[cur][0] = h[d2][0];
                    t[cur][1] = h[d1][1];
                }
                if (k1 >= 0 && k2 < 0) {
                    temp = h[d2][0] * h[d2][1] * t[k1][1];
                    t[cur][0] = h[d2][0];
                    t[cur][1] = t[k1][1];
                }
                if (k1 >= 0 && k2 >= 0) {
                    temp = t[k2][0] * t[k2][1] * t[k1][1];
                    t[cur][0] = t[k2][0];
                    t[cur][1] = t[k1][1];
                }
                re += temp;
                stack.push(String.valueOf(cur++));
            } else {
                stack.push(s);
            }
        }
        return re;
    }

    public static void main(String[] args) {
        Scanner sa = new Scanner(System.in);
        while (sa.hasNext()) {
            int x = Integer.parseInt(sa.nextLine());
            int[][] m1 = new int[x][2];
            for (int i = 0; i < x; i++) {
                String temp = sa.nextLine();
                String[] ss = temp.split(" ");
                m1[i][0] = Integer.parseInt(ss[0]);
                m1[i][1] = Integer.parseInt(ss[1]);
            }
            String str = sa.nextLine();
            List<String> inList = new ArrayList<>();
            for (int i = 0; i < str.length(); i++) {
                inList.add(String.valueOf(str.charAt(i)));
                if (Character.isLetter(str.charAt(i))) {
                    if (Character.isLetter(str.charAt(i + 1)) || str.charAt(i + 1) == '(') {
                        inList.add("*");
                    }
                }
                if (str.charAt(i) == ')' && (i+1<str.length()&&(Character.isLetter(str.charAt(i+1))||str.charAt(i+1)=='('))) {
                    inList.add("*");
                }
            }
            for (String s : inList) {
                System.out.print(s + "");
            }
            int root = build(inList, 0, inList.size());
            post(root);
//            for (String s : postList) {
//                System.out.print(s + "");
//            }
            int result = cal(postList, m1);
            postList.clear();
            System.out.println(result);
        }
    }