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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            //矩阵个数
            int n = in.nextInt();
            //矩阵大小：按序存入
            List<List<Integer>> list = new ArrayList<>();
            //矩阵大小
            for (int i = 0; i < n; i++) {
                List<Integer> li = new ArrayList<>();
                //行数
                int x = in.nextInt();
                //列数
                int y = in.nextInt();
                li.add(x);
                li.add(y);
                list.add(li);
            }
            //计算表达式
            String rule = in.next();
            //表达式栈
            Stack<Character> stack = new Stack<>();
            //表达式中每个矩阵出现的位置
            Map<Character, Integer> map = new HashMap<>();
            //矩阵的位置
            int count = 0;
            //计算顺序
            List<String> order = new ArrayList<>();
            for (int i = 0; i < rule.length(); i++) {
                char ch = rule.charAt(i);
                if (Character.isLetter(ch)) {
                    //是矩阵名，记录名称和位置
                    map.put(ch, count);
                    count++;
                    //名称入栈，计算优先级
                    stack.push(ch);
                } else if (ch == '(') {
                    stack.push(ch);
                } else {
                    StringBuilder s = new StringBuilder();
                    while (stack.peek() != '(') {
                        char op = stack.pop();
                        s.append(op);
                    }
                    //左括号出栈
                    stack.pop();
                    //表达式保存：反转顺序与输入保持一致
                    String exp = s.reverse().toString();
                    order.add(exp);
                }
            }
            //如A(BC)式，栈可能不为空
            while (!stack.isEmpty()) {
                order.add(stack.pop() + "");
            }
            //保存整个表达式按序计算后的矩阵的大小
            int[] Arr = new int[] {0, 0};
            //整个表达式的计算量：每一部分的计算量之和
            int total = 0;
            for (String s : order) {
                //某部分的计算量
                int sum = 0;
                //计算s得到的矩阵大小，若s为单个矩阵，则是该矩阵的大小
                int[] tempArr = new int[] {0, 0};
                for (int i = 0; i < s.length(); i++) {
                    int c = map.get(s.charAt(i));
                    //获取第c个数组大小
                    List<Integer> size = list.get(c);
                    if (tempArr[0] != 0) {
                        int compute = tempArr[0] * tempArr[1] * size.get(1);
                        sum += compute;
                        //更新
                        tempArr[1] = size.get(1);
                    } else {
                        //临时数组初始化值
                        tempArr[0] = size.get(0);
                        tempArr[1] = size.get(1);
                    }
                }
                total += sum;
                if (Arr[0] != 0) {
                    //B(CD)式,先计算CD
                    int d = 0;
                    if (Arr[0] == tempArr[1]) {
                        total+= tempArr[0] * tempArr[1] * Arr[1];
                        Arr[0] = tempArr[0];
                    } else if (Arr[1] == tempArr[0]) {
                        //(BC)D式，计算BC
                        total+= Arr[0] * Arr[1] * tempArr[1];
                        Arr[1] = tempArr[1];
                    }
                } else {
                    Arr[0] = tempArr[0];
                    Arr[1] = tempArr[1];
                }
            }
            System.out.println(total);
        }
    }
}

每次做字符串的题都会怀疑自己是不是不适合写算法，纯纯暴力小子