前言：
今天同学们对“java求矩阵相邻元素的和”大体比较关怀，咱们都想要了解一些“java求矩阵相邻元素的和”的相关资讯。那么小编在网摘上汇集了一些有关“java求矩阵相邻元素的和””的相关知识，希望咱们能喜欢，小伙伴们一起来学习一下吧！【矩阵连乘求乘法次数问题】
题目：输入n个矩阵（矩阵名称为大写英文字母表示）的维度和一些矩阵链乘表达式，输出乘法的次数，也就是计算量。如果乘法无法进行，输出error。假定A是m×n矩阵，B是n×p矩阵，那么A乘B是m×p矩阵，乘法次数为m×n×p，一般我们把乘法次数称之为本次计算的计算量。如果A的列数不等于B的行数，则乘法无法进行。
例如：A是50×10的，B是10×20的，C是20×5的，则(A(BC))的乘法次数为10×20×5（BC的乘法次数）+ 50×10×5（(A(BC))的乘法次数）= 3500。两次乘法的计算量之和。
【输入形式】
矩阵个数n。
下面n行分别为n个矩阵的名称、行数和列数。
需要计算的矩阵连乘的表达式。
【输出形式】
给出表达式的计算量（为n-1次乘法的计算量之和）
【样例输入】
3
A 10 5
B 5 6
C 6 7
(A(BC))
【样例输出】
560
解题思路： 本题需要根据矩阵的表达式来规定计算的顺序，需要通过栈的数据结构来解决计算的先后问题，可以从表达式的左括号和右括号寻找突破点，例如读到一个左括号就向栈里放入一个矩阵，读到一个右括号就计算一个矩阵得出新的矩阵并记录乘法次数，重复上述步骤，直到栈空为止，得出最终的结果。
【详细分析】：
首先需声明变量以及定义栈。
int Matrix_length = in.nextInt(); //矩阵个数
int[] Matrix = new int[Matrix_length*2];
Matrix_length为矩阵的个数，数组Matrix用于存放矩阵的行列值。
int[] stack1 = new int[s.length()]; //行值
int[] stack2 = new int[s.length()]; //列值
int top = 0; //栈指针
int j = 0; //用于遍历 Matrix
int times = 0;
其中，stack1用于存放矩阵的行值，stack2用于存放矩阵的列值，两个栈共用一个栈指针top ，j 用于遍历数组Matrix.偶数（j * 2）位用于存储行值，奇数位（j * 2+1）用于存储列值。
本例中Matrix[ ] = {10,5,5,6,6,7}
static final String S = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
定义矩阵字母表
for(int i=0;i<Matrix_length;i++){ //输入矩阵行列值
b[i] = in.next().charAt(0);
Matrix[i*2] = in.nextInt();
Matrix[i*2+1] = in.nextInt();
}
String s = in.next(); //输入矩阵连乘表达式
输入矩阵和矩阵表达式：A 10 5 B 5 6 C 6 7 (A(BC))
for(int i=0;i<Matrix.length/2-1;i++){//判断矩阵是否符合连乘条件
if(Matrix[i*2+1]!=Matrix[(i+1)*2]) {
return 0;
}
}
进行矩阵连乘之前需要判断这些矩阵是否符合连乘条件，即判断相邻矩阵的列值和行值是否相等。
核心语句：
for(int i=0;i<s.length();i++){ //入栈
if(s.charAt(i)=='(') {
if (s.charAt(i + 1) != '(') { //找到最内层左括号时矩阵入栈
stack1[top] = Matrix[j * 2];
stack2[top] = Matrix[j * 2 + 1];
j++;
top++;
}
}
else if(S.indexOf(s.charAt(i))!=-1&&s.charAt(i-1)==')'){ //字母左边为右括号需提前top++
top++;
}
else if(s.charAt(i)==')'){ //出栈
if(j*2<Matrix.length&&s.charAt(i-1)!=')'){ //遇到第一个右括号时矩阵入栈
stack1[top] = Matrix[j * 2];
stack2[top] = Matrix[j * 2 + 1];
j++;
}
times += stack1[top]*stack2[top]*stack1[top-1];
stack2[top-1] = stack2[top]; //相乘后所得新矩阵的列值
top--;
if(top==0&&j*2<Matrix.length){ //栈空但矩阵未完成遍历
top++;
}
}
}
return times;
}
从左向右依次扫描表达式s的字符，读到最内层的左括号（右边为矩阵字母）时读入一个矩阵，将其放入栈中，top++, 读到第一个右括号（右括号左边为矩阵字母）时，放入一个矩阵并计算times值，并得到新的矩阵的行列值，其行列值将上一个矩阵的行列值覆盖，top -1。else if(S.indexOf(s.charAt(i))!=-1&&s.charAt(i-1)==')'){ //字母左边为右括号需提前top++
top++;
}
不过也有特殊的情况，如(A((BC)D)) , 在读到最后一个右括号时，需读入D矩阵，而在读入矩阵C后，top-1，得到新的矩阵时top还指在新的矩阵，这时需要我们提前top++来防止读入的矩阵D将新的矩阵行列值覆盖。
【举例分析】: A 10 5 、B 5 6 、C 6 7，(A(BC))
【完整代码】：
public class Solution {
static final String S = "ABCDEFGHIJKLMN";
public static int solution(String s,int[] Matrix){
int[] stack1 = new int[s.length()]; //行值
int[] stack2 = new int[s.length()]; //列值
int top = 0; //栈指针
int j = 0; //用于遍历 Matrix
int times = 0;
for(int i=0;i<Matrix.length/2-1;i++){ //判断矩阵是否符合连乘条件
if(Matrix[i*2+1]!=Matrix[(i+1)*2]) {
return 0;
}
}
for(int i=0;i<s.length();i++){ //入栈
if(s.charAt(i)=='(') {
if (s.charAt(i + 1) != '(') { //找到最内层左括号时矩阵入栈
stack1[top] = Matrix[j * 2];
stack2[top] = Matrix[j * 2 + 1];
j++;
top++;
}
}
else if(S.indexOf(s.charAt(i))!=-1&&s.charAt(i-1)==')'){ //字母左边为右括号需提前top++
top++;
}
else if(s.charAt(i)==')'){ //出栈
if(j*2<Matrix.length&&s.charAt(i-1)!=')'){ //遇到第一个右括号时矩阵入栈
stack1[top] = Matrix[j * 2];
stack2[top] = Matrix[j * 2 + 1];
j++;
}
times += stack1[top]*stack2[top]*stack1[top-1];
stack2[top-1] = stack2[top]; //相乘后所得新矩阵的列值
top--;
if(top==0&&j*2<Matrix.length){ //栈空但矩阵未完成遍历
top++;
}
}
}
return times;
}
测试类：
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int Matrix_length = in.nextInt(); //矩阵个数
int[] Matrix = new int[Matrix_length*2];
char[] b = new char[Matrix_length]; //矩阵大写字母，对计算无用
for(int i=0;i<Matrix_length;i++){ //输入矩阵行列值
b[i] = in.next().charAt(0);
Matrix[i*2] = in.nextInt();
Matrix[i*2+1] = in.nextInt();
}
String s = in.next(); //输入矩阵连乘表达式
if(solution(s,Matrix)==0) { //不符合连乘条件
System.out.println("error");
}else{
System.out.println(solution(s, Matrix));
}
}
}
样例输出：
你们学会了吗？
标签： #java求矩阵相邻元素的和
