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

import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static int res = 0;
    private static int x =0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[][] arr = new int[n][2];
            for(int i=0; i<n; i++) {
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            in.nextLine();
            String str = in.nextLine();
            process(arr, str);
            System.out.println(res);
        }
    }

    private static int[] process(int[][] arr, String str) {
        Stack<int[]> stack = new Stack<>();
        for(int i=0; i < str.length(); i++) {
            int[] q;
            //遇到括号优先处理括号中的表达式
            if(str.charAt(i) == '(') {
                int c = 1;
                int s = i++;
                while(c != 0) {
                    if(i >= str.length()) {
                        break;
                    }
                    if(str.charAt(i) == ')') {
                        c--;
                    }else if(str.charAt(i) == '('){
                        c++;
                    }
                    i++;
                }
                String child = str.substring(s+1, i-1);
                q = process(arr, child);
                i--;
            } else {
                q = arr[x++];
            }
            
            //栈中有值，与栈中的值相乘，否则入栈
            if(!stack.isEmpty()) {
                int[] s = stack.pop();
                res += mul(s[0], s[1], q[1]);
                int[] ab = AMulB(s, q);
                stack.push(ab);
            } else {
                stack.push(q);
            }
        }
        return stack.pop();
    }

    //相乘后返回的矩阵
    private static int[] AMulB(int[] a, int[] b) {
        return new int[]{a[0],b[1]};
    }

    //矩阵相乘需要的乘法次数
    private static int mul(int a, int b, int c) {
        return a * b * c;
    }
}