题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
// 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; } }