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

import java.util.Scanner;
import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            Queue<Matrix> matrixList = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                matrixList.add(new Matrix(sc.nextInt(),sc.nextInt()));
            }
            Stack<Matrix> stack = new Stack<>();
            int sum = 0;
            String str = sc.next();
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (Character.isLetter(c)) {
				  //如果是矩阵就从队列离取出来入栈
                    stack.push(matrixList.poll());
                } else if (c == ')') {
				  //如果是)则从栈里取两个出来计算重新入栈，后取的放前面运算
                    Matrix matrix2 = stack.pop();
                    Matrix matrix1 = stack.pop();
				  //次数是（x.y）*(y*z)=(x,z),乘的次数是x*y*z
                    sum += matrix1.x*matrix1.y*matrix2.y;
                    stack.push(new Matrix(matrix1.x, matrix2.y));
                }
            }
            System.out.println(sum);
        }
    }

    public static class Matrix {
        private int x;
        private int y;

        public Matrix(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}