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

1、栈的顺序是后进先出，存的时候按照左行，左列，右行，右列存。取得时候应该是右列，右行，左列，左行。

2、两个矩阵相乘时是按照左边得所有行依次与右边的每一列相乘 然后乘以左边的列（或者右边的行，此时左列和右行一定相等，否则无法进行矩阵计算）。故计算公式count+= leftRow * rightColumn* leftColumn

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static int count =0;
    private static int[][] arr;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            // 定义一个数组接受当前信息
            int n=in.nextInt();
            arr = new int[n][2];
            for (int i=0;i<n;i++) {
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            // 解析当前输入规则
            String orderStr = in.next();
            getCount(orderStr);
            System.out.print(count);
        }
    }

    public static void getCount(String orderStr){

        Stack<Integer> stack=new Stack<>();
        for (char c:orderStr.toCharArray()) {
            if (c =='(') {
                continue;
            } else if (c==')') {
                // 连续取两个队列信息
                int rightColumn=stack.pop();
                int rightRow=stack.pop();
                int leftColumn=stack.pop();
                int leftRow=stack.pop();
                count+= leftRow * rightColumn* leftColumn;// 此时左列一定等于右行。否则匹配失败
                // 计算后得到的新矩阵为 左行 * 右列
                stack.push(leftRow);
                stack.push(rightColumn);
            } else {
                // 正常情况，需要把数据存进去
                int index = c-65;
                stack.push(arr[index][0]);
                stack.push(arr[index][1]);
            }
        }
    }
}