HJ70. 矩阵乘法计算量估算

刷题

题目：矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵。计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。编写程序计算不同的计算顺序需要进行的乘法次数。

数据范围：矩阵个数：1≤n≤15，行列数：1≤rowi,coli≤100，保证给出的字符串表示的计算顺序唯一。
进阶：时间复杂度：O(n)，空间复杂度：O(n)

输入描述：输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则。计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！
输出描述：输出需要进行的乘法次数
链接：https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b

栈相关的需要画图，图画出来就明白了

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[][] nums = new int[n][2];
            for(int i=0; i<n; i++){
                nums[i][0] = sc.nextInt();
                nums[i][1] = sc.nextInt();
            }
            String s = sc.next();
            Stack<Integer> stack = new Stack<>();
            int count=0;
            for(int i=s.length()-1,j=n-1; i>=0; i--){
                char c=s.charAt(i);
                if(c>='A' && c<='Z'){
                    stack.push(nums[j][0]);//行
                    stack.push(nums[j][1]);//列
                    j--;
                } else if (c=='('){
                    //倒序遍历+行先入栈，所以先出来的是y
                    Integer y=stack.pop();
                    Integer x=stack.pop();
                    Integer z=stack.pop();
                    stack.pop();//出栈的是 y
                    //计算量
                    count+=x*y*z;
                    //再把x,z加进去
                    stack.push(x);
                    stack.push(z);
                }
            }
            System.out.println(count);
        }
    }
}