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

总体没有特别需要解释的。

比较在意的一点：如果出现(A(ABC)D)，类似这种一个括号里有超过2个矩阵的例子，应该如何计算。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[][] matrix=new int[n][2];//储存矩阵内容
        for(int i=0;i<n;i++){
            matrix[i][0]=scan.nextInt();
            matrix[i][1]=scan.nextInt();
        }
        String input=scan.next();//输入的计算法则

        //输出结果
        System.out.println(solve(matrix,input));
    }

    //解决方案
    public static int solve(int[][] matrix, String input){
        int sum=0;
        Stack<Integer> stack=new Stack<>();//储存参与运算的矩阵
        for(int i=0;i<input.length();i++){
            char item=input.charAt(i);
            int location=item-'A';
            //如果字符为字母，则将该字母对应矩阵内容放入栈中，并记录存储了1个矩阵
            if(item<='Z' && item>='A'){
                stack.push(matrix[location][0]);
                stack.push(matrix[location][1]);
            }else if(item==')'){//如果字符为“）”，则表示第一个括号结束，可以开始计算
                    int y1=stack.pop();
                    int x1=stack.pop();
                    int y0=stack.pop();
                    int x0=stack.pop();
                    //计算乘法次数，并加入sum
                    sum+=x0*y0*y1;
                    //将新得到的矩阵放入栈中
                    stack.push(x0);
                    stack.push(y1);
            }else if(item=='('){
                continue;
            }
            
        }
        return sum;
    }
}