题解 | #矩阵乘法计算量估算# 编译原理：语法归约

看到这种若干个符号合并为一个符号的操作就想到了编译原理的语法归约操作，条件反射了属于是。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 有点类似编译原理中对语法的归约处理
        while (in.hasNextInt()) {
            int n = in.nextInt();
            // 这里暂时记录输入的行和列
            List<int[]> list = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                list.add(new int[]{in.nextInt(), in.nextInt()});
            }

            String expr = in.next();
            Deque<Node> stack = new ArrayDeque<>();
            int sum = 0;
            for (char ch : expr.toCharArray()) {
                switch (ch) {
                    case '(':
                        stack.push(Node.LEFT);
                        break;
                    case ')': {
                        // 输入右括号，不断弹出符号，直到弹出左括号，将它们记录到 nodeList 中
                        Deque<Node> nodeList = new ArrayDeque<>();
                        while (stack.peek() != Node.LEFT) {
                            Node pop = stack.pop();
                            nodeList.addFirst(pop);
                        }
                        // 弹出左括号
                        stack.pop();
                        // 从左到右，每次计算两个矩阵的乘积，消除两个矩阵，得到新的矩阵
                        // 新矩阵的行数和第一个矩阵相同，列数和第二个矩阵相同
                        while (nodeList.size() > 1) {
                            Node first = nodeList.removeFirst();
                            Node second = nodeList.removeFirst();
                            sum += first.row * first.col * second.col;
                            nodeList.addFirst(new Node(first.name + second.name, first.row, second.col));
                        }
                        // 合并后剩下的矩阵重新添加到栈中
                        Node node = nodeList.removeFirst();
                        stack.push(node);
                        break;
                    }
                    default:
                        // 添加矩阵到栈中
                        stack.push(new Node(ch + "", list.get(ch - 'A')[0], list.get(ch - 'A')[1]));
                }
            }
            System.out.println(sum);
        }
    }

    public static class Node {
        // 左括号
        static final Node LEFT = new Node("(", -1, -1);

        String name;
        int row;
        int col;

        public Node(String name, int row, int col) {
            this.name = name;
            this.row = row;
            this.col = col;
        }
    }
}