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

// mark一下
// 1. 和四则运算类题目一致 使用双栈求解
// 2. ( 直接入栈；字母直接入栈；)就进行一次计算
// 3. 计算后的结果，入栈时，将 AB 一个整体作为新的操作数入栈 并缓存其对应的矩阵的行列数
// 4. 需要保证整个输入表达式被小括号包围 如果没有 手动添加 保证能完全计算 且 最后不需要再进行判断 操作符栈必定能为空
// 5. 进行手写模拟 以熟悉过程

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            int n = Integer.valueOf(in.nextLine());
            Stack<String> numStack = new Stack<>();
            Stack<String> opStack = new Stack<>();
            Map<String, String> hashMap = new HashMap<>();
            char c = 'A';
            for (int i = 0; i < n; i++) {
                String eachLine = in.nextLine();
                hashMap.put(String.valueOf((char) (c + i)), eachLine);
            }
            String rule = in.nextLine();
            // 需要最外层括号包裹
            // rule = "(" + rule + ")";
            int length = rule.length();
            int ans = 0;
            for (int i = 0; i < length; i++) {
                char curC = rule.charAt(i);
                String curCStr = String.valueOf(curC);
                if (curC == '(') {
                    opStack.push(curCStr);
                } else if (curC >= 'A' && curC <= 'Z') {
                    numStack.push(curCStr);
                } else if (curC == ')') {
                    // 和四则运算不一致的地方：每次遇到)都进行一次计算即可
                    // while (!opStack.isEmpty() && !opStack.peek().equals("(")) {
                        String l2 = numStack.pop();
                        String l1 = numStack.pop();
                        String num2 = hashMap.get(l2);
                        String num1 = hashMap.get(l1);
                        ans += calc(num1, num2);
                        numStack.push(l1 + l2);
                        hashMap.put(l1 + l2, num1.split(" ")[0] + " " + num2.split(" ")[1]);
                    // }
                    // opStack.pop();
                }
            }

            // 最外层有一对括号 所以不用类似表达式计算一样继续算

            System.out.println(ans);
        }
    }

    public static int calc(String num1, String num2) {
        int x = Integer.valueOf(num1.split(" ")[0]);
        int y = Integer.valueOf(num1.split(" ")[1]);
        int z = Integer.valueOf(num2.split(" ")[1]);
        return x * y * z;
    }
}