矩阵乘法计算量估算

题目中有运算顺序要求，想到用栈解决，要知道(m, n) * (n, p)矩阵的运算量为n * p * m，强烈建议把矩阵画出来验证！
把控制台输入的矩阵都保存到数组matrices中，用栈来处理输出顺序。遍历表达式中的每个字符，
①字母，把该矩阵的（行， 列）压入栈待计算。②左括号（，忽略
③右括号，依次弹出matrices里的两个矩阵B、A，用n * p * m计算运算量，加到res里。
并把计算完的矩阵（行， 列）->(A的行， B的列)重新入栈，参与后续计算。计算完成后返回res值即可。
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int res = 0;
        List<int[]> matrices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int row = in.nextInt();
            int col = in.nextInt();
            matrices.add(new int[] {row, col});
        }
        Stack<int[]> order = new Stack<>();
        String expression = in.next();
        for (int j = 0; j < expression.length(); j++) {
            if (Character.isLetter(expression.charAt(j))) {
                int index = expression.charAt(j) - 'A';
                order.push(matrices.get(index));
            } else if (expression.charAt(j) == ')') {
                int[] matrixB = order.pop();
                int[] matrixA = order.pop();
                res += matrixA[1] * matrixA[0] * matrixB[1];
                order.add(new int[] {matrixA[0], matrixB[1]});
            }

        }
        System.out.println(res);
    }
}

import java.util.Scanner; 
import java.util.HashMap;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int count = 0;
        // 这个哈希表保存了一个(字母,数组)对，分别表示矩阵名称和行列数
        HashMap<Character, int[]> mats = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int[] m = new int[2];
            for (int j = 0; j < 2; j++) {
                m[j] = in.nextInt();
            }
            mats.put((char)(i+65), m);
        }
        String exp = in.next();
        ArrayList<Character> stack = new ArrayList<>();
        for (char c : exp.toCharArray()) {
            String min = "";
            if (c == ')') {
                while (stack.get(stack.size()-1) != '(') {
                    min += stack.remove(stack.size()-1);
                }
                stack.remove(stack.size()-1);  // 消除括号
                int[] temp = compute(mats, min);
                count += temp[0] * temp[1] * temp[2];
                mats.remove(min.charAt(0));
                mats.remove(min.charAt(1));    // 删除旧矩阵
                int[] cu = {temp[2], temp[0]};  // 新矩阵的行列
                mats.put(min.charAt(0), cu);  // 给计算后的新矩阵重新命名
                stack.add(min.charAt(0));  // 再正常入栈
            } else {  // 正常入栈
                stack.add(c);
            }
        }
        System.out.print(count);
    }

    public static int[] compute(HashMap<Character, int[]> mats, String exp) {
        int[] r = {mats.get(exp.charAt(0))[1], mats.get(exp.charAt(0))[0],
                    mats.get(exp.charAt(1))[0]};
        return r;
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int count = in.nextInt();
            List<int[]> list = new ArrayList<>();
            for (int i = 0 ; i < count ; i ++) {
                list.add(new int[] {in.nextInt(), in.nextInt()});
            }
            String algorithm = in.next();

            Stack<int[]> num = new Stack<>();
            Stack<Character> symbol = new Stack<>();
            int sum = 0 ;
            int m = 0;
            for (int i = 0 ; i < algorithm.length() ; i ++) {

                if (algorithm.charAt(i) == '(') {
                    symbol.push('(');
                } else if (algorithm.charAt(i) == ')') {
                    if(num.size()>=symbol.size()){
                        sum += cals(num,symbol);
                    }
                    symbol.pop();
                } else {
                    num.push(list.get(m++));
                    int charIndex = i - 1;
                    while (charIndex >= 0 && algorithm.charAt(charIndex) != '(' &&
                            algorithm.charAt(charIndex) != ')') {
                        charIndex--;
                        sum += cals(num, symbol);
                    }
                }
            }
            while (!symbol.isEmpty() && num.size() > 1) {
                sum += cals(num, symbol);
            }
            System.out.println(sum);
        }
    }
    public static int cals(Stack<int[]> num, Stack<Character> opts) {
        if (num.isEmpty() || num.size() < 2) {
            return 0;
        }
        if (opts.isEmpty()) {
            return 0;
        }
        int[] b = num.pop(), a = num.pop();
        num.push(new int[] {a[0], b[1]});  
        return  b[0] * a[0] * b[1];
    }
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        Matrix[]  matrixs = new Matrix[n];
        for (int i = 0; i < n; i++) {
            String[] ss = in.nextLine().split(" ");
            Matrix m = new Matrix(Integer.parseInt(ss[0]), Integer.parseInt(ss[1]));
            matrixs[i] = m;
        }
        String expr = in.nextLine();
        // 表达式算法 采用递归dfs来计算，并汇总乘法次数
        dfs(matrixs, expr);
        System.out.println(num);
    }

    private static int num = 0;
    static Matrix dfs(Matrix[] ms, String expr) {
        Matrix mm = null; // 上一个矩阵
        boolean isFirst = true; // 判断是否是第一个矩阵
        for (int i = 0; i < expr.length(); i++) {
            if (isFirst && i > 0) {
                isFirst = false;
            }
            Matrix cu = null; // 当前矩阵
            char ch = expr.charAt(i);
            if (ch == '(') {
                int count = 1;
                int j = i + 1;
                while (count > 0) {
                    if (expr.charAt(j) == '(') {
                        count++;
                    } else if (expr.charAt(j) == ')') {
                        count--;
                    }
                    j++;
                }
                cu = dfs(ms, expr.substring(i + 1, j - 1));
                i = j - 1;
            }
            // 当前字符表示矩阵
            if (cu == null) {
                cu = ms[ch - 'A'];
            }
            // 首个矩阵不参与计算
            if (isFirst) {
                mm = cu;
                continue;
            }
            // 计算乘法次数，得到新的矩阵
            num += mm.getRows() * mm.getCols() * cu.getCols();
            mm = new Matrix(mm.getRows(), cu.getCols());
        }
        return mm;
    }
}

class Matrix {
    private int rows; // 矩阵行数
    private int cols; // 矩阵列数

    public Matrix(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
    }

    int getRows() {
        return this.rows;
    }

    int getCols() {
        return this.cols;
    }
}

知识点： 栈 和 矩阵乘法的理解(值得一看)

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            int length = input.nextInt();
            int i = 0;
            HashMap<Character, Node> map = new HashMap<>(length);
            while (i < length) {
                Node node = new Node(input.nextInt(), input.nextInt());
                char key = (char) (65 + i);
                map.put(key, node);
                i++;
            }
            String rule = input.next();
            System.out.println(caculateTimes(map, rule));
        }
    }

    private static int caculateTimes(Map<Character, Node> data, String rules) {
        int result = 0;
        Stack<Node> stack = new Stack<>();
        while (true) {
            int startPos = rules.lastIndexOf("(");
            int endPos = rules.indexOf(")", startPos);
            if (endPos - startPos < 3) {
                break;
            }
            Node currentNode = '_' == rules.charAt(startPos + 1) ?  stack.pop() : data.get(rules.charAt(startPos + 1));
            Node nextNode = '_' == rules.charAt(startPos + 2) ? stack.pop() : data.get(rules.charAt(startPos + 2)); ;
            result += currentNode.getRow() * currentNode.getColumn() * nextNode.getColumn();
            stack.add(new Node(currentNode.getRow(), nextNode.getColumn()));
            rules = rules.replace(rules.substring(startPos, endPos + 1),  "_");
        }
        return result;
    }

    static class Node {
        private Integer row;

        private Integer column;

        public Node(Integer row, Integer column) {
            this.row = row;
            this.column = column;
        }

        public Integer getRow() {
            return row;
        }
        public Integer getColumn() {
            return column;
        }
    }
}
​

import java.util.*;

// （AB）C=50*10*20+50*20*5 A(BC）=10*20*5+10*5*50
public class Main {
    private static int data[][], sum = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String subExpression;
        int num = in.nextInt();
        data = new int[num][2];
        for (int i = 0; i < num; i++) {
            data[i][0] = in.nextInt();
            data[i][1] = in.nextInt();
        }

        String expression = in.next();
        String resultSubExpression = "";
        while (!resultSubExpression.equals(expression)) {
            int firstBracketsIndex = expression.indexOf(")");
             int lastBracketsIndex =-1;
            //  char c='';
            for (int i = firstBracketsIndex; i >=0; i--) {
             
                if(expression.charAt(i)=='('){
                    lastBracketsIndex = i;
                    break;
                }
            }
            subExpression = expression.substring(lastBracketsIndex, firstBracketsIndex + 1);
            resultSubExpression = calculationAmount(subExpression);
            expression = expression.replace(subExpression, resultSubExpression);


        }
        System.out.println(sum);
        // }
    }

    private static String calculationAmount(String subExpression) {
        subExpression = subExpression.replace("(", "").replace(")", "");
        int len = subExpression.length();
        int [][] subData = new int[len][2];
        String resultSubExpression = null;
        char c;
        int index;
        for (int i = 0; i < len; i++) {
            c = subExpression.charAt(i);
            index = c - 'A';
            subData[i][0] = data[index][0];
            subData[i][1] = data[index][1];
            resultSubExpression = c + "";
        }


        for (int i = 1; i < len; i++) {
            c = subExpression.charAt(i);
            index = c - 'A';
            sum += (subData[i - 1][0] * subData[i - 1][1] * subData[i][1]);
            data[index][0] = subData[i - 1][0];

        }

        return resultSubExpression;
    }
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[][] matrixSize = new int[n][2];
        for (int i = 0; i < n; i++) {
            matrixSize[i][0] = sc.nextInt();
            matrixSize[i][1] = sc.nextInt();
            sc.nextLine();
        }
        String str = sc.nextLine();
        //map的 key为给定的矩阵名称 value为给定矩阵的行和列
        HashMap<String, int[]> map = new HashMap<>();
        int index = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= 65 && str.charAt(i) <= 90) {
                map.put(String.valueOf(str.charAt(i)), new int[]{matrixSize[index][0],matrixSize[index][1]});
                index++;
            }
        }
        Stack<String> stack = new Stack<>();
        int multiplicationCnt = 0;
        for (char s : str.toCharArray()) {
            if (s == '(' || (s >= 'A' && s <= 'Z')) {
                stack.push(String.valueOf(s));
            } else if (s == ')') {
                StringBuilder sb = new StringBuilder();
                while (!"(".equals(stack.peek())) {
                    //先弹出来的是后入的
                    String matrix2 = stack.pop();
                    String matrix1 = stack.pop();
                    sb.append(matrix1).append(matrix2);
                    int[] size1 = map.get(matrix1);
                    int[] size2 = map.get(matrix2);
                    int[] sizeNew = new int[]{size1[0],size2[1]};
                    //将这两个矩阵相乘后构成的新矩阵存入map中
                    map.put(sb.toString(), sizeNew);
                    //计算这两个矩阵的乘法量
                    multiplicationCnt += size1[0]*size2[1]*size1[1];
                }
                stack.pop();//消除上述')'对应的'('
                //将相乘后新的矩阵压入栈中
                stack.push(sb.toString());
            }
        }
        System.out.println(multiplicationCnt);
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i=0; i<n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        System.out.println(cul(arr, sc.next()));
    }
}

// 计算矩阵计算数
public static int cul(int[][] arr, String express) {
    Stack<Character> stack = new Stack<>();
    Stack<int[]> matrixStack = new Stack<>();
    int[] temp;
    int times = 0;
    // 入栈（分字符栈，数组栈）
    for (char c : express.toCharArray()) {
        // 遇到')'，出栈计算，计算完重新入栈
        if (c == ')') {
            stack.pop();
            temp = matrixStack.pop();
            while (stack.pop() != '(') {
                times += matrixStack.peek()[0] * temp[0] * temp[1];
                temp = new int[]{matrixStack.pop()[0], temp[1]};
            }
            stack.push('t');
            matrixStack.push(temp);
            continue;
        }
        // 符号入栈，若符号不为'('，则数组也入栈
        stack.push(c);
        if (c != '(') {
            matrixStack.push(arr[c - 'A']);
        }
    }
    return times;
}