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

import java.util.*;

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

    public static int solution(int[][] arr,String str){
        int count = 0;
        Stack<int[]> stack = new Stack<>();
        for(int i = 0,j=0 ;i<str.length();i++){
            char c = str.charAt(i);
            //遇到左括号，跳过
            if(c == '('){
                continue;
            }
            //遇到字母，入栈
            if(c >= 'A' && c<='Z'){
                stack.push(arr[j++]);
            }
            //遇到右括号，弹出两个并计算，再入栈
            if(c == ')'){
                int[] a = stack.pop();
                int[] b = stack.pop();
                //a是最后入栈的，b是倒数第二个 即b * a
                count += a[0] * a[1] * b[0];
                stack.push(new int[]{b[0],a[1]});
            }
        }
        return count;
    }
}