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

矩阵的乘法

已知矩阵A：[m, n]，矩阵B：[n, p]，那么A * B的结果是[m ,p]，需要的运算次数是m * n * p。

这是前提知识，了解这个之后下一步就是如何判断运算顺序。

运算顺序

首先需要定义一个二维数组来保存矩阵。

我的想法是这样的，以(A(BC))为例，从尾到头遍历一次，遇到字母则将矩阵最后一行压栈，遇到“(”则弾栈，将结果进行相乘操作。

代码

package huawei;

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[][] a = new int[n][2];

            for (int i = 0; i < n; i++) {
                a[i][0] = in.nextInt();
                a[i][1] = in.nextInt();
            }

            String rule = in.next();

            int sum = 0;
            Stack<Integer> stack = new Stack<>();
            for (int i = rule.length() - 1, j = n -1; i >= 0; i--) {
                if (rule.charAt(i) >= 'A' && rule.charAt(i) <= 'Z') {
                    stack.push(a[j][1]);
                    stack.push(a[j][0]);
                    j--;
                } else if (rule.charAt(i) == '(') {
                    int x0 = stack.pop();
                    int y0 = stack.pop();
                    int x1 = stack.pop();
                    int y1 = stack.pop();
                    sum += x0 * y0 * y1;
                    stack.push(y1);
                    stack.push(x0);
                }
            }
        System.out.println(sum);
        }
    }
}