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

解题思路：

• 使用逆波兰表达式的设计， 根据题意可以得出规律： 右括号可以代替为 “*”，做括号为空的字符串。
• 逆波兰表达式： 遇到数字直接入栈， 遇到符号 弹出栈中俩个数字进行计算，并将结果入栈。
• 栈中，可以存储字母对应的xy坐标，这里注意入栈的顺序，后面计算时候需 先进后出。
• 矩阵乘法的次数 count += ax * ay * by;
• 最后建议将栈中的最后一个元素弹出，防止内存泄漏。

import java.util.*;

// import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // 此题实现的基础：
        // 1. 表达式求值 （双栈 或者  逆波兰表达式）  HJ50 四则运算
        // 2. 矩阵乘法的实现

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int n = in.nextInt();

            // 读取矩阵 行和列
            // 每一行分别是对应字母的x和y
            int[][] matrix = new int[n][2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 2; j++) {
                    matrix[i][j] = in.nextInt();
                }
            }

            // 读取计算规则
            String expression = in.next();
            System.out.println(getAnalysisExpression(expression, matrix));
        }
    }

    // 表达式解析 (长度为 字母表)
    public static int getAnalysisExpression(String expression, int[][] matrix) {
        // 构建逆波兰表达式 (数字直接入栈，遇到符号时 弹出两个数字进行计算 并压入栈)
        expression = expression.replace("(", "").replace(")", "*");
        Stack<Integer> stack = new Stack<>();

        int count = 0;
        for (int i = 0; i < expression.length(); i++) {
            // 此题中这里，不是字母就是乘号
            char value = expression.charAt(i);
            // 是字母
            if (Character.isLetter(value)) {
                // 入栈 横纵坐标
                int index = value - 'A';
                stack.add(matrix[index][0]);
                stack.add(matrix[index][1]);
            } else {
                // 是"（"
                int by = stack.pop();
                stack.pop();
                int ay = stack.pop();
                int ax = stack.pop();

                // 矩阵乘法的次数
                count += ax * ay * by;

                // 入栈 乘积结果
                stack.add(ax);
                stack.add(by);
            }
        }
        stack.pop();

        return count;
    }
}