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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * 矩阵乘法计算量估算
 * eg:((AB)C),(C(AB)),这里没规定必须是按照字母顺序出现的,故将字母与矩阵数组联系起来是个问题
 * 解决:遍历字母出现和数组下标的顺序是一致的,设置了一个rank标志将数组合字母联系起来
 * stack也可以存int[]
 * 这里与四则运算不同,都是乘法,不必考虑运算顺序,
 * 题目说保证给出的字符串表示的计算顺序唯一,故每两个元素一定是有括号的
 * 即这里给的直接就是后缀表达式,遇到)就相当于是*.
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] v= new int[N][2];
        for (int i = 0; i < N; i++) {
            String[] t=br.readLine().split(" ");
            v[i][0]=Integer.parseInt(t[0]);
            v[i][1]=Integer.parseInt(t[1]);
        }
        String s=br.readLine();
        char[] op = s.toCharArray();
        Stack<int[]> stack= new Stack<>();
        int rank=0;
        int res=0;
        for (int i = 0; i < op.length; i++) {
            if(Character.isAlphabetic(op[i]))
                stack.push(v[rank++]);
            else if(op[i]==')') {
                int[] o2=stack.pop();
                int[] o1=stack.pop();
                res+=o1[0]*o1[1]*o2[1];
                stack.push(new int[]{o1[0],o2[1]});
            }
        }
        System.out.println(res);
    }
}