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

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 2; j++) {
                    arr[i][j] = in.nextInt();
                }
            }
            String express = in.next();
            solution(arr, express);
        }
    }

    private static void solution(int[][] arr, String express) {

        Stack<int[]> stack = new Stack<>();
        int res = 0;
        int count = 0;
        for (int i = 0; i < express.length(); i++) {
            if (express.charAt(i) == '(') {
                continue;
            } else if (express.charAt(i) == ')') {
                int[] a1 = stack.pop();
                int[] a2 = stack.pop();
                // a2为前面的数组
                int[] newArr = {a2[0], a1[1]};
                res += a2[0] * a2[1] * a1[1];
                stack.push(newArr);
            } else {
                stack.push(arr[count++]);
            }
        }
        if (stack.size() == 1) {
            System.out.println(res);
            return;
        }

        List<int[]> list = new ArrayList<>();
        while (stack.size() > 0) {
            list.add(stack.pop());
        }
        int[] tmp = list.get(list.size() - 1);
        for (int i = list.size() - 2; i >= 0; i--) {
            int[] a = list.get(i);
            res += tmp[0] * tmp[0] * a[1];
            tmp = new int[] {tmp[0], a[1]};
        }

    }
}