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

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);
        while (in.hasNextInt()) { // 注意 while 处理多个 case0. 
            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 type = in.next();
            System.out.println(getCount(n,arr,type));
        }
    }
    private static int getCount(int i,int[][] b,String type){
       // System.out.println(i+"===="+b.length+"===="+type.length());
        int sum = 0;
        char [] cs = type.toCharArray();
        Stack<Integer> st = new Stack<Integer>();

        for(int j=type.length()-1,k=i-1;j>=0;j--){
            if(cs[j]!='(' && cs[j]!=')'){
                st.push(b[k][1]);
                st.push(b[k][0]);
                //System.out.println(b[k][1]+"====="+cs[j]+"========"+b[k][0]);
                k--;
            }else if(cs[j]=='('){
                //从右向遍历遇到左括号，出栈，计算后把新矩阵入栈，其实可以可以从左到右遇到右括号的话，出栈计算
                int a0=st.pop(),a1=st.pop(),a2=st.pop(),a3=st.pop(); 
                sum += a0*a1*a3;
                //System.out.println(a0+"*"+a1+"*"+a3);
                st.push(a3);
                st.push(a0);
            }           
        }
        return sum;
    }
}

}