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

import java.util.*;

/**
 * @author hll[yellowdradra@foxmail.com]
 * @date 2022-10-13 21:36
 **/
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Matrix[] matrix = new Matrix[in.nextInt()];
        fill(matrix, in);
        String s = in.nextLine();
        LinkedList<Matrix> stack = new LinkedList<Matrix>();
        int multiplications = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                continue;
            } else if (s.charAt(i) == ')') {
                Matrix a = stack.pop();
                Matrix b = stack.pop();
                // 矩阵乘法是不满足交换律的 注意出栈顺序
                multiplications += b.multiply(a);
                stack.push(b);
            } else {
                stack.push(matrix[s.charAt(i) - 'A']);
            }
        }
        System.out.println(multiplications);
    }

    static void fill(Matrix[] arr, Scanner in) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Matrix(in.nextInt(), in.nextInt());
        }
        // 吞一个回车 要不还要转换 有点麻烦
        in.nextLine();
    }

    static class Matrix {
        int x, y;

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

        int multiply(Matrix b) {
            int t = this.x * this.y * b.y;
            this.y = b.y;
            return t;
        }
    }
}