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

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();
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            String expression = String.valueOf(in.next());
            Stack<Integer> stack = new Stack<>();
            int result = 0;
            int index = expression.length() - 1;
		   //从后往前读取expression,分别按照‘(’,‘)’,[A-Z]三种情况操作栈
            while (index >= 0) {
                char c = expression.charAt(index);
                if (c == ')') {//')'直接入栈，存为0作为区分
                    stack.push(0);
                } else if (c >= 'A' && c <= 'Z') {//[A-Z]，矩阵，直接存行列长度入栈，为一对，注意顺序
                    int row = arr[c - 65][0];
                    int col = arr[c - 65][1];
                    stack.push(row);
                    stack.push(col);
                } else { //'('出栈，计算矩阵相乘的新矩阵，出栈到最后一个栈值为0
                    int y0 = stack.pop();
                    int x0 = stack.pop();
                    int y1 = stack.pop();
                    int x1 = stack.pop();
                    result += x0 * x1 * y1;
                    int flag = stack.pop();
                    while (flag != 0) { //一个括号里存在超过两个矩阵
                        y1 = flag;
                        x1 = stack.pop();
                        result += x0 * x1 * y1;
                        flag = stack.pop();
                    }
                    stack.push(x0);
                    stack.push(y1);
                }
                index--;
            }
            System.out.println(result);
        }
    }
}