矩阵乘法计算量估算

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;
}

时间超过100% 内存超过98.88%
来来回回改了好久 菜鸡也要坚持！
1、一个栈记录字符 一个栈记录矩阵规格
2、去括号 并更新
3、最后遍历统计结果

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[][] str = new String[n][2];
        String s;
        for(int i=0;i<n;i++){
            s = br.readLine();
            str[i] = s.split(" ");
        }
        int res = 0; // 统计乘法次数
        String pat = br.readLine(); // 结合方式

        // 利用栈记录结合顺序转为矩阵规格并输出
        Stack stack = new Stack(); // 记录所有字符
        Stack sst = new Stack();  // 只记录数组规格
        // 遍历结合方式 去除括号
        for(char ch : pat.toCharArray()){
            if(ch != ')'){
                stack.push(ch);
                if(ch!='('){
                    sst.push(new int[]{Integer.parseInt(str[ch-'A'][0]),Integer.parseInt(str[ch-'A'][1])}); 
                }
            } else {
                Stack st = new Stack();  // 临时存放计算括号内的矩阵
                while(stack.pop()!='('){
                    st.push(sst.pop());
                }
                if(st.size()<=1){
                    if(st.size()==1){
                        sst.push(st.pop());
                    }
                    continue;       // 若括号内的元素为1或0 表示括号无效 删除左括号并继续运算即可
                }
                // 放入计算后的新矩阵大小并将左括号弹出
                int[] tmp = st.pop(); // 弹出第一个规格元素并不断更新
                while(!st.isEmpty()){
                    int[] arr = st.pop();
                    int count = tmp[0]*arr[1]; // 相乘后的结果元素数
                    res += count * tmp[1];
                    tmp[1] = arr[1];
                }
                stack.push(' '); // 保持stack指针与sst一致 故随意加了个空格
                sst.push(tmp); // 最后把tmp输入回栈内
            }
        }
        // 遍历栈 统计结果 注意出栈为倒序 先颠倒回来
        Stack stRes = new Stack();
        while(!sst.isEmpty()){
            stRes.push(sst.pop());
        }
        int[] tmp = stRes.pop();
        while(!stRes.isEmpty()){
            int[] arr = stRes.pop();
            int count = tmp[0]*arr[1]; // 相乘后的结果元素数
            res += count * tmp[1];
            tmp[1] = arr[1];
        }
        System.out.println(res);
    }
}