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

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            int n = in.nextInt();
            int[][] matrix = new int[n][2];
            for (int i = 0; i < n; i++) {
                matrix[i][0] = in.nextInt();
                matrix[i][1] = in.nextInt();
                in.nextLine();
            }
            char[] ex = in.nextLine().toCharArray();
            Deque<Integer> deque = new ArrayDeque<>();
            int index = 0;
            int sum = 0;
            for (int i = 0; i < ex.length; i++) {
                if (ex[i] == '(') { // 遇到左括号，跳过
                    continue;
                }
                if (Character.isLetter(ex[i])) { // 行列数入栈
                    deque.push(matrix[index][0]);
                    deque.push(matrix[index][1]);
                    index++;
                    if (i == ex.length - 1) { // 最后一个矩阵，结算
                        sum += compute(deque);
                        break;
                    }
                    if (i > 0 && Character.isLetter(ex[i - 1]) && Character.isLetter(ex[i + 1])) {
                        // 上一个符号与下一个符号都是矩阵符号，结算一次
                        sum += compute(deque);
                    }
                    continue;
                }
                if (ex[i] == ')' && deque.size() >= 4) {
                    sum += compute(deque); // 遇到右括号，若栈内有矩阵则结算一次
                }
            }
            while (deque.size() >= 4) { // 结算到栈中的矩阵小于两组为止
                sum += compute(deque);
            }
            System.out.println(sum);
        }
    }

    private static int compute(Deque<Integer> deque) {
        int y1 = deque.pop();
        int y0 = deque.pop();
        int x1 = deque.pop();
        int x0 = deque.pop();
        // 将计算后的行列数入栈
        deque.push(x0);
        deque.push(y1);
        return x0 * x1 * y1;
    }
}