题解 | #矩阵乘法计算量估算# 递归找括号

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
class Matrix{
    int row;
    int col;
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int count=0;
    private static Matrix cal(Matrix a,Matrix b){
        count+=(a.col*b.col*a.row);
        Matrix result=new Matrix();
        result.row=a.row;
        result.col=b.col;
        return result;
    }
    private static Matrix fun(Matrix[] m,String exp){
        List<Matrix> list=new ArrayList<>();
        char[] cs=exp.toCharArray();
        for(int i=0;i<cs.length;i++){
            if(cs[i]=='('){
                int temp=1,j=i+1;
                //找到最外层的括号
                while(temp>0){
                    if(cs[j]=='(')
                        temp++;
                    else if(cs[j]==')')
                        temp--;
                    j++;
                }
                //递归找内层括号
                Matrix result=fun(m,exp.substring(i+1,j-1));
                list.add(result);
                i=j-1;
            }
            if(cs[i]-'A'>=0 && cs[i]-'Z'<=0){
                list.add(m[cs[i]-'A']);
            }
            //如果本层有两个元素了就计算
            if(list.size()==2){
                Matrix result=cal(list.get(0),list.get(1));
                list.clear();
                list.add(result);
            }
        }
        return list.get(0);
    }

    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int num=Integer.valueOf(s.nextLine());
        Matrix[] matrices=new Matrix[num];
        int i=0;
        while(i<num){
            Matrix matrix=new Matrix();
            matrices[i]=matrix;
            String[] cs=s.nextLine().split(" ");
            matrices[i].row=Integer.valueOf(cs[0]);
            matrices[i].col=Integer.valueOf(cs[1]);
            i++;
        }
        String exp=s.nextLine();
        s.close();
        Matrix result=fun(matrices,exp);
//        System.out.println(result.row+" "+result.col+" "+count);
        System.out.println(count);
    }
}