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

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        Map<Character, Integer[]> map = new HashMap<>();
        for (int i = 0; i < count; i++) {
            map.put((char)('A' + i)
                    , new Integer[] {in.nextInt(), in.nextInt()});
        }

        String rule = in.next();
        LinkedList<Character> stack = new LinkedList<>();

        long total = 0l;

        for (int i = 0; i < rule.length(); i++) {
            char c = rule.charAt(i);
            if (c == '(' || Character.isAlphabetic(c)) {
                stack.push(c);
            } else if (c == ')') {
                List<Character> list = new ArrayList<>();
                while (!stack.isEmpty() && stack.peek() != '(') {
                    list.add(stack.pop());
                }
                // (
                stack.pop();

                Collections.reverse(list);
                Integer[] m = map.get(list.get(0));
                for (int j = 1; j < list.size(); j++) {
                    Integer[] currm = map.get(list.get(j));
                    total += (m[0] * m[1] * currm[1]);
                    m = new Integer[]{m[0], currm[1]};
                }

                char key = (char)('A' + count++);
                stack.push(key);
                map.put(key, m);
            }
        }

        System.out.println(total);
    }
}