题解 | #矩阵乘法计算量估算#

使用栈辅助进行解决，类似于求表达式的解

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] dim = new int[n][2];
        for(int i = 0; i < n; i++){
            dim[i][0] = sc.nextInt();
            dim[i][1] = sc.nextInt();
        }
        
        sc.nextLine();
        String method = sc.nextLine();
        Item[] items = new Item[method.length()];
        int index = 0;
        for(int i = 0; i < method.length(); i++){
            char c = method.charAt(i);
            if(c == '('){
                items[i] = new Item(1);
            }else if(c == ')'){
                items[i] = new Item(2);
            }else{
                items[i] = new Item(3, dim[index][0], dim[index][1]);
                index++;
            }
        }
        int ans = 0;
        Deque<Item> stack = new LinkedList<>();
        for(int i = 0; i < items.length; i++){
            //栈顶    当前
            // (     字符     压栈
            // (     (       压栈
            // 字符   (       压栈
            // 字符   字符    弹栈 计算 在压栈
            // 字符   )       //弹栈两次，将左括号弹出，并且当前元素置为原来栈顶
            // (      )      弹栈
            // )      字符
            //  )     (
            Item item = items[i];
            if(stack.isEmpty()){
                stack.push(item);
            }else if(stack.peek().type==1){
                stack.push(item);
            }else if(item.type == 1 && stack.peek().type == 3){
                stack.push(item);
            }else if(item.type == 3 && stack.peek().type == 3){
                Item A = stack.pop();
                Item B = item;
                Item C = new Item(3, A.m, B.n);
                ans += A.m * B.n * A.n;
                stack.push(C);
            }else if(item.type == 2 && stack.peek().type == 3){
                Item peek = stack.pop();
                stack.pop(); //弹出左括号
                //压入peek
                if(stack.isEmpty() || stack.peek().type == 1){
                    stack.push(peek);
                }else if(stack.peek().type == 3){
                    Item A = stack.pop();
                    Item B = peek;
                    Item C = new Item(3, A.m, B.n);
                    ans += A.m * B.n * A.n;
                    stack.push(C);
                }
            }
        }
        System.out.println(ans);
        
    }
    
    static class Item{
        int type; //0表示( ;1表示) ;3表示矩阵
        int m; //如果是矩阵
        int n; //如果是矩阵
        
        Item(int type){
            this.type = type;
        }
        Item(int type, int m, int n){
            this.type = type;
            this.m = m;
            this.n = n;
        }
    }
    
}