描述

矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：

A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵

计算A*B*C有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。

编写程序计算不同的计算顺序需要进行的乘法次数。   本题含有多组样例输入！ 数据范围：数据组数：，矩阵个数：，行列数： 进阶：时间复杂度：，空间复杂度：

 

输入描述：

输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则
计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！

输出描述：

输出需要进行的乘法次数

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.Collector;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 获取矩阵相关信息
        while (sc.hasNextInt()) {
            int matrixNum = sc.nextInt();
            char matrixName = 'A';
            List<Matrix> matrixs = new ArrayList<Matrix>();
            for (int i = 0; i <  matrixNum; i++) {
                Matrix matrix = new Matrix();
                matrix.setName(String.valueOf(matrixName));
                matrix.setRow(sc.nextInt());
                matrix.setCol(sc.nextInt());
                matrixs.add(matrix);
                matrixName++;
            }
            // 使用Deque队列做一个先进后出计算,并生成计算后的矩阵到matrixs
            String cal = sc.next();
            Deque<String> queueMatrix = new LinkedList<String>();
            // 乘法次数
            int multiplication = 0;
            for (int i = 0; i < cal.length(); i++) {
                if(cal.charAt(i) == ')') {
                    List<String> matrixNames = new ArrayList<String>();
                    // 弹出两个矩阵
                    matrixNames.add(queueMatrix.pollLast());
                    matrixNames.add(queueMatrix.pollLast());
                    // 弹出左括号
                    queueMatrix.pollLast();
                    // 获取要计算的两个矩阵
                    List<Matrix> matrixCal = matrixs.stream().filter(o->matrixNames.contains(o.getName())).collect(Collectors.toList());
                    Matrix matrix1 = matrixCal.get(0);
                    int row1 = matrix1.getRow();
                    int col1 = matrix1.getCol();
                    String name1 = matrix1.getName();
                    Matrix matrix2 = matrixCal.get(1);
                    int row2 = matrix2.getRow();
                    int col2 = matrix2.getCol();
                    String name2 = matrix2.getName();
                    // 两个矩阵可以相乘的条件是一个矩阵的列等于一个矩阵的行
                    // 两个矩阵乘法的次数 = 不相等的行数 * 不相等的列数 * 相等的行列数
                    if(col1  == row2) {
                        multiplication += row1 * col1 * col2;
                        // 若队列中还有元素则，将计算的新队列构建到矩阵集合以及FILO队列中
                        if(!queueMatrix.isEmpty()) {
                            Matrix temp = new Matrix();
                            temp.setRow(row1);
                            temp.setCol(col2);
                            temp.setName(name1 + name2);
                            queueMatrix.add(name1 + name2);
                            matrixs.add(temp);
                        }
                    } else {
                        multiplication += row1 * col1 * row2;
                        if(!queueMatrix.isEmpty()) {
                            Matrix temp = new Matrix();
                            temp.setRow(row2);
                            temp.setCol(col1);
                            temp.setName(name1 + name2);
                            queueMatrix.add(name1 + name2);
                            matrixs.add(temp);
                        }
                    }
                } else {
                    queueMatrix.add(String.valueOf(cal.charAt(i)));
                }
            }
            System.out.println(multiplication);
        }    
        
    }

    public static class Matrix {
        private int row;
        private int col;
        private String name;

        public int getRow() {
            return row;
        }

        public void setRow(int row) {
            this.row = row;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int col) {
            this.col = col;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }    
    }
}