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

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();//矩阵个数
            ArrayList<matrix> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                matrix m = new matrix(in.nextInt(), in.nextInt());
                list.add(m);
            }
            String rule = in.next();
            Stack stack = new Stack<>();
            int j = 0;
            int cnt = 0;
            for (int i = 0; i < rule.length(); i++) {
                if (rule.charAt(i) == '(') stack.push(rule.charAt(i));
                else if (Character.isLetter(rule.charAt(i))) {
                    stack.push(list.get(j++));
                } else {
                    matrix m1 = (matrix) stack.pop();
                    matrix m2 = (matrix) stack.pop();
                    stack.pop();
                    matrix m12 = m2.multiply(m1);
                    cnt += m12.row * m12.column * m2.column;
                    stack.push(m12);
                }
            }
            System.out.println(cnt);
        }
    }
}

class matrix {
    public int row;
    public int column;

    public String name;

    public matrix(int row, int column) {
        this.row = row;
        this.column = column;
    }

    public matrix multiply(matrix m) {
        return new matrix(row, m.column);
    }
}