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

1. 遇到'('压栈，如果栈顶是'('或者为空栈，矩阵字母直接进栈
2. 遇到')',弹出两个矩阵进行计算，次顶元素 * 栈顶元素
3. 计算量估计 ：矩阵： A * B 矩阵 B * C，计算的结果为：A * B * C，最后将运算的结果相加起来即可

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static class Node{
        // 分别用来保存输入的行列，以及对应的矩阵
        int row;
        int col;
        char c;// 如果是计算过的节点，统一替换为 ‘#’
    }
    public static void main(String[] args) {
        // A x B * B * A 的矩阵相乘的计算量是 : A * B * A
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int num = sc.nextInt();
            String s = sc.nextLine();// 接收输入了int型数据之后的换行
            Node[] node = new Node[num];
            for(int i = 0 ; i < num;i++)
                node[i] = new Node();
            for(int i = 0; i < num;i++){
                node[i].row = sc.nextInt();
                node[i].col = sc.nextInt();
                node[i].c = (char)('A' + i);
            }
            String s2 = sc.nextLine();
            // 输入表达式
            StringBuffer bf = new StringBuffer(sc.nextLine());
            Stack<Character> stack = new Stack<>();
            Queue<Character> queue = new ArrayDeque<>();// 临时存放逆波兰算式的队列
            int res = 0;
            for(int i = 0;i < bf.length();i++){
                char c = bf.charAt(i);
                // 遍历表达式，做压栈处理
                if(stack.empty() || stack.peek() == '(' || c == '(')// 如果栈顶是空，或者栈定元素是'(';直接入栈
                {
                    stack.push(c);
                }else if(Character.isLetter(c)){
                    stack.push(c);
                }else if(c == ')'){
                    while(true) {
                        if (stack.peek() == '(') {
                            // 如果栈顶的元素是(,那么就直接将(出局
                            stack.pop();
                            break;
                        } else {
                            // 将两个操作数入队
                            char operNum1 = stack.pop();
                            char operNum2 = stack.pop();// operNum2 * operNum1
                            // 计算结果，然后将结果压栈
                            int row = 0;
                            int col1 = 0;
                            int col2 = 0;
                            int index = 0;
                            for(int k = 0;k < num;k++){
                                if(node[k].c == operNum2){
                                    // 保存行
                                    row = node[k].row;
                                    col1 = node[k].col;
                                    node[k].c = '#';
                                }
                                if(node[k].c == operNum1){
                                    // 保存列
                                    col2 = node[k].col;
                                    index = k;
                                    node[k].c = '#';
                                }
                            }
                            // 将第k和节点设置为结果节点，改变行
                            node[index].row = row;node[index].col = col2;node[index].c = operNum1;
                            // 结果为
                            res += row * col1 * col2;
                            // 将结果压入栈，矩阵为operNum1
                            if(stack.peek() != '(')// 因为前面没有将'('弹出去，如果直接将计算的结果压栈，到时候计算不准确
                            stack.push(operNum1);
                            else{
                                stack.pop();// 先将'(' 出栈在压栈
                                stack.push(operNum1);
                                break;
                            }
                        }
                    }
                }
            }
             System.out.println(res);
        }
    }
}