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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[][] str = new String[n][2];
        String s;
        for(int i=0;i<n;i++){
            s = br.readLine();
            str[i] = s.split(" ");
        }
        int res = 0; // 统计乘法次数
        String pat = br.readLine(); // 结合方式
        
        // 利用栈记录结合顺序转为矩阵规格并输出
        Stack<Character> stack = new Stack<>(); // 记录所有字符
        Stack<int[]> sst = new Stack<>();  // 只记录数组规格
        // 遍历结合方式 去除括号
        for(char ch : pat.toCharArray()){
            if(ch != ')'){
                stack.push(ch);
                if(ch!='('){
                    sst.push(new int[]{Integer.parseInt(str[ch-'A'][0]),Integer.parseInt(str[ch-'A'][1])}); 
                }
            } else {
                Stack<int[]> st = new Stack<>();  // 临时存放计算括号内的矩阵
                while(stack.pop()!='('){
                    st.push(sst.pop());
                }
                if(st.size()<=1){
                    if(st.size()==1){
                        sst.push(st.pop());
                    }
                    continue;       // 若括号内的元素为1或0 表示括号无效 删除左括号并继续运算即可
                }
                // 放入计算后的新矩阵大小并将左括号弹出
                int[] tmp = st.pop(); // 弹出第一个规格元素并不断更新
                while(!st.isEmpty()){
                    int[] arr = st.pop();
                    int count = tmp[0]*arr[1]; // 相乘后的结果元素数
                    res += count * tmp[1];
                    tmp[1] = arr[1];
                }
                stack.push(' '); // 保持stack指针与sst一致 故随意加了个空格
                sst.push(tmp); // 最后把tmp输入回栈内
            }
        }
        // 遍历栈 统计结果 注意出栈为倒序 先颠倒回来
        Stack<int[]> stRes = new Stack<>();
        while(!sst.isEmpty()){
            stRes.push(sst.pop());
        }
        int[] tmp = stRes.pop();
        while(!stRes.isEmpty()){
            int[] arr = stRes.pop();
            int count = tmp[0]*arr[1]; // 相乘后的结果元素数
            res += count * tmp[1];
            tmp[1] = arr[1];
        }
        System.out.println(res);
    }
}