矩阵的乘法
已知矩阵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);
}
}
}