一问题描述

假设你必须评估一种表达式，比如 ABCD，其中A、B、C、D 是矩阵。因为矩阵乘法满足结合律，所以乘法的顺序是任意的。矩阵连乘的乘法次数由相乘的顺序决定。例如5010、1020、205 的矩阵。现有两种方案计算ABC，即 ABC 和 A*(B*C)。第一种要进行 15000次乘法运算，而第2种只进行 3500 次乘法运算。写程序，计算给定矩阵表达式需要进行多少次乘法运算。

输入：输入包含矩阵和表达式两部分。第1部分，第1行包含一个整数n（1<n<26）,代表矩阵的个数，接下来的 n 行，每行都包含一个大写组么来表示矩阵的名称，以及两个整数来表示矩阵的行数和列数。第2部分是一个矩阵或矩阵表达式。

输出：对于一个表达式，如果乘法无法进行，则输出“Error”，否则输出所需的乘法运算次数。

输入样例
9

A 50 10

B 10 20

C 20 5

D 30 35

E 35 15

F 15 5

G 5 10

H 10 20

I 20 25

A

B

C

（AA）

（AB）

（AC）

（A(BC)）

（（AB）C）

（(（（（DE）F）G）H)I）

（D（E（F（G（HI）））））

（（D（EF））（（GH）I））

输出样例

0

Error

10000

Error

3500

15000

40500

47500

15125

二问题分析

首先需要搞清楚下面3个问题。

什么是矩阵可乘？
矩阵相乘后的结果？
两个矩阵相乘需要多少次运算？

1 什么是矩阵可乘？

如果第1个矩阵的列等于等2个矩阵的行，那么这两个矩阵可乘。

2 矩阵相乘后的结果？

两个矩阵相差的结果，其行、列分别等于第个矩阵的行、第2个矩阵的列。

3 两个矩阵相乘需要多少次运算？

A（mn）和A（nk）相乘执行乘法运算的次数为 mnk

三算法设计

1 首先将矩阵及行列值存储在数组中。

2 读入一行矩阵表达式。

3 遇到矩阵名称时入栈，遇到右括号时出栈。两个矩阵 m2、m1，如果 m1 的列不等于 m2 的行，则矩阵不可乘，标记 error=true 并退出循环，否则计算乘法运算的次数，并将两个矩阵相乘后的结果入栈。

4 如果 error = true，则输出“error”，否则输出乘法运算的次数。

四图解

1 以输入样例(A(BC))为例，其中 A 50 10，B 10 20，C 20 5，字母表示矩阵名，后两个数字分别表示该矩阵的行和列。遇到左括号什么都不做，遇到右括号则入栈，首先 ABC 入栈，如下图所示。

2 遇到右括号时出栈。两个矩阵 C、B，B 10 20，C 20 5;B 的列等于C的行，两个矩阵是可乘的，乘法运算的次数为 10 * 20 * 5 = 1000，结果矩阵 X 的行为 B 的行 10，X 的列为 C 的列 5，即 X 10 5，将结果入栈。

3 遇到右括号时出栈。两个矩阵 A、X，A 10 10，X 10 5;A 的列等于X的行，两个矩阵是可乘的，乘法运算的次数为 50 * 10 * 5 = 2500，累计次数为 1000+2500=3500，结果矩阵 Y 的行为 A 的行 50，Y 的列为 X 的列 5，即 Y 50 5，将结果入栈。

4 表达式读入完毕，输出结果 3500

四代码

package stackdemo;

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

public class MatrixDemo {
    public static void main(String[] args) {
        Stack<Matrix> s = new Stack<>();
        Scanner scanner = new Scanner(System.in);
        // 矩阵的个数
        int n = scanner.nextInt();
        Matrix[] m = new Matrix[n];
        for (int i = 0; i < m.length; i++) {
            m[i] = new Matrix();
        }

        for (int i = 0; i < n; i++) {
            char c = scanner.next().charAt(0);
            int k = c - 'A'; // 转换为整数
            m[k].a = scanner.nextInt();
            m[k].b = scanner.nextInt();
        }

        while (true) {
            String str = scanner.next();
            int len = str.length();
            boolean error = false;
            int ans = 0;
            for (int i = 0; i < len; i++) {
                if (Character.isLetter(str.charAt(i))) {
                    s.push(m[str.charAt(i) - 'A']);
                } else if (str.charAt(i) == ')') {
                    Matrix m2 = s.pop();
                    Matrix m1 = s.pop();
                    if (m1.b != m2.a) {
                        error = true;
                        break;
                    }
                    ans += m1.a * m1.b * m2.b;
                    s.push(new Matrix(m1.a, m2.b));
                }
            }
            if (error) {
                System.out.println("error");
            } else {
                System.out.println(ans);
            }
        }
    }
}

class Matrix {
    int a; // 矩阵的行
    int b; // 矩阵的列

    public Matrix(int a, int b) {
        this.a = a;
        this.b = b;
    }

    public Matrix() {
    }
}

五测试

绿色为输入，白色为输出

矩阵乘法问题

一问题描述