矩阵乘法计算量估算

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

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

public class HJ70 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        String s = sc.next();
        int sum = 0;//总数
        //初始化数据完成
        Stack<HJ70Node> mp = new Stack<>();
        int temI = 0;
        HJ70Node currentNode ;
        for (int i = 0; i < s.length(); i++) {
            HJ70Node item;
            if(s.charAt(i) >='A' && s.charAt(i)<='Z'){
                 item = new HJ70Node(a[temI][0] , a[temI][1]);
                 temI ++ ;
            }else{
                 item = new HJ70Node(s.charAt(i));
            }
//            System.out.println(item);
            if(item.type == ' '){
                if(mp.empty()){
                    mp.add(item);
                }else {//上一个也是矩阵的时候，计算乘积
                    if(mp.peek().type == ' '){
                        HJ70Node preNode = mp.pop();
                        sum += preNode.x * preNode.y * item.y;
                        mp.push(new HJ70Node(preNode.x , item.y));
                    }else{
                        mp.push(item);
                    }
                }
            } else if (item.type == '(') {
                mp.add(item);
            }else{//当符号为右括号时候，出栈计算。这时候括号内应该只有一个元素
                HJ70Node preOne = mp.peek();//右括号前一个肯定是矩阵
                mp.pop();
                HJ70Node preTwo = mp.peek();//右括号前二个肯定是左括号
                mp.pop();
//                if(preTwo.type=='('){
//                    mp.add(preOne);
//                }
                if(mp.size()>0 && mp.peek().type==' '){
                    sum += mp.peek().x * mp.peek().y * preOne.y;
                    HJ70Node preThree =  mp.pop();
                    mp.push(new HJ70Node(preThree.x,preOne.y));
                }else{
                    mp.push(preOne);
                }
            }
        }
        System.out.println(sum);

    }

}

//压栈元素类
class HJ70Node{
    public char type;//括号符号或者 为空串
    public int x;//如果是矩阵，则为纵向个数/行数
    public int y;//如果是矩阵，则认为横向个数/列数
    public HJ70Node(char type){
        this.type = type;
    }
    public HJ70Node(int x , int y){
        this.type = ' ';
        this.x= x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "node : type-"+this.type+" x:"+this.x+" y:"+this.y;
    }
}