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

import java.util.*;

// 想不出好的解决思路，暂时硬解。利用栈处理括号带来的计算优先级的变化
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int n = Integer.parseInt(in.nextLine());
            int[][] arrs = new int[n][2];
            for (int i = 0; i < n; i++) {
                String[] split = in.nextLine().split(" ");
                arrs[i][0] = Integer.parseInt(split[0]);
                arrs[i][1] = Integer.parseInt(split[1]);
            }
            String com = in.nextLine();
            System.out.println(count(arrs, com));
        }
    }

    public static int count(int[][] arrs, String com) {
        List<String> stack = new ArrayList<>();
        int n = com.length(), off = 0, total = 0;
        for (int i = 0; i < n; i++) {
            if (com.charAt(i) == '(') {
                stack.add(com.charAt(i) + "");
            } else if (Character.isLetter(com.charAt(i))) {
                stack.add(arrs[off][0] + "#" + arrs[off][1]);
                off++;
            } else {
                List<String> list = new ArrayList<>();
                while (!stack.get(stack.size() - 1).equals("(")) {
                    list.add(0, stack.remove(stack.size() - 1));
                }
                stack.remove(stack.size() - 1);
                String[] temp = compute(list);
                total += Integer.parseInt(temp[0]);
                stack.add(temp[1]);
            }
        }
        total += Integer.parseInt(compute(stack)[0]);
        return total;
    }

    public static String[] compute(List<String> list) {
        int t = 0;
        String[] res = new String[2];
        if (list.size() == 1) {
            res[0] = "0";
            res[1] = list.get(0);
        }
        String start = list.remove(0);
        while (!list.isEmpty()) {
            String cur = list.remove(0);
            String[] s_ = start.split("#"), c_ = cur.split("#");
            Integer one = Integer.parseInt(s_[0]);
            Integer two = Integer.parseInt(s_[1]);
            Integer three = Integer.parseInt(c_[1]);
            t += one * two * three;
            start = one + "#" + three;
        }
        res[0] = t + "";
        res[1] = start;
        return res;
    }
}