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

import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            // int a = in.nextInt();
            // int b = in.nextInt();
            // System.out.println(a + b);
            int n = in.nextInt();
            int a[][] = new int[n][2]; // 存放行、列
            for (int i = 0; i < n; i++) {
                a[i][0] = in.nextInt();
                a[i][1] = in.nextInt();
            }
            String s = in.next(); // 计算公式 A(BC)
            Deque<Integer> queue = new LinkedList<>(); // 存放矩阵的行数和列数
            int sum = 0;
            for (int i = 0, j = 0; i < s.length(); i++) {
                if (s.charAt(i) >= 'A' &&
                        s.charAt(i) <= 'Z') { // 属于字母则把相应的行数、列数加入队列
                    queue.offer(a[j][0]);
                    queue.offer(a[j][1]);
                    j++;
                } else if (s.charAt(i) == ')') {
				  // 从 last 依次取出
                    int x0 = queue.pollLast(), y0 = queue.pollLast();
                    int x1 = queue.pollLast(), y1 = queue.pollLast();
                    sum += x0 * y0 * y1;
                    queue.offer(y1); // 存入时，要遵从FIFO 的基本规则
                    queue.offer(x0);
                }
            }
            System.out.println(sum);
        }
    }
}

双向队列有时候可以解决很多问题，尤其适合数据存储到容器后又要逆向取出来的场景。比如 LRUCache