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

import java.util.Scanner;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args)  throws IOException {
        // Scanner in = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //1、顺序执行、2、记录中间结果、3、记录（行）列
        String str = null;
        while ((str = br.readLine()) != null) {
            int num = Integer.parseInt(str); //总数量
            int[][] arr = new int[num][2];
            for (int i = 0; i < num; i++) {
                String[] sa = br.readLine().split(" ");
                arr[i][0] = Integer.parseInt(sa[0]);
                arr[i][1] = Integer.parseInt(sa[1]);
            }
            int n = arr.length - 1; //几个矩阵
            char [] ca = br.readLine().toCharArray(); //A(BC)
            Stack<Integer> stack = new Stack<>();
            int sum = 0;
            for (int i = ca.length - 1; i >= 0; i--) { //A(CB)
                char one = ca[i];
                if (one == ')') {
                    stack.push(-1);

                } else if (one == '(') {
                    int n1 = stack.pop(); //B
                    int n2 = stack.pop(); //C
                    sum += arr[n1][0] * arr[n2][0] * arr[n2][1];
                    arr[n1][1] = arr[n2][1]; //共同的列等于
                    stack.pop();//栈：先进后出，）先进的所以后出要在pop一次
                    stack.push(n1);//中间结果的列存入//改变记录行列的数组值
                } else {
                    stack.push(n);//不直接存放ABC 存放的是第几个矩阵的索引
                    n--;//当前矩阵的数字
                }


            }
            System.out.println(sum);


        }






    }
}

栈：先进后出

(A（BC）)=》

1、）

2、)

3、C

4、B

( --》弹出B\C,计算后，再弹出）。然后压入中间结果temp

1、）

2、temp

3\A

4\( -》》》弹出A、temp,计算结果压入，此时for循环遍历完，输出sum