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

其实思路就是表达式求值

但是在细节上被卡了好久（头一次知道了，List 可以存Integer[]）

以下代码，可以处理括号内矩阵数量>=3 的情况

如：（ABC）、A(BCDE)

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int count = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        Integer[][] s = new Integer[n][2];

        for(int i = 0; i < n; i ++){
            for(int j = 0; j < 2; j ++){
                s[i][j] = in.nextInt();
            }
        }

        String str = in.next();

        //递归
        Integer[] y = deal(s, str); 
  
        System.out.println(count);
    }

    public static Integer[] deal(Integer[][] s, String str){
        List<Integer[]> list = new ArrayList<Integer[]>();
        for(int i = 0; i < str.length(); i ++){
            char a = str.charAt(i);
            if(a >= 'A' && a <= 'Z'){
                list.add(s[a - 'A']);
            }
            if(a == '('){
                int j = i + 1;
                int tmp = 1;
                while(tmp != 0){
                    if(str.charAt(j) == '('){
                        tmp ++;
                    }
                    if(str.charAt(j) == ')'){
                        tmp --;
                    }
                    j ++;
                }
                list.add(deal(s, str.substring(i + 1, j - 1)));
                i = j - 1;
            }
        }
        int sum = 0;
        Integer[] z = list.get(0);
        for(int i = 1; i < list.size(); i ++){
            sum = sum + (z[0] * list.get(i)[1] * z[1]);
            z[1] = list.get(i)[1];
        }
        count += sum;
        return z;
    }

    
}