题解 | #矩阵乘法计算量估算#从后往前遍历，遇到字母入栈，遇到'('出栈，计算之后再入栈

我觉得题目有个条件没说清楚，就是不存在没有ABC这种没有括号的情况，必须是两两括号括起来；例如：((AB)C),(A(BC)),((AB)(CD))

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            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 s = in.next();
            int sum = 0;
            //从后往前遍历
            Stack<Integer> stack = new Stack<Integer>();
            for(int i=s.length()-1,j=n-1;i>=0;i--){
                if(Character.isLetter(s.charAt(i))){
                    stack.push(arr[j][1]);//先压列
                    stack.push(arr[j][0]);//再压行
                    j--;
                }else if(s.charAt(i) == '('){//遇到左括号，弹出栈顶的两个矩阵，计算之后再压栈
                    int x0 = stack.pop(),y0 = stack.pop();//先进后出，先出来的是行
                    int x1 = stack.pop(),y1 = stack.pop();
                    sum += x0 * y0 * y1;//此时y0和x1必然是相等的，否则两个矩阵不能运算
                    stack.push(y1);//先压列
                    stack.push(x0);
                }
            }
            System.out.println(sum);
        }
    }
}