刷华为机考的同学应该对“矩阵乘法计算量估算”这道题不陌生。题目名字听起来像线性代数应用题真正上手才发现它考的是字符串解析和栈模拟核心是让你按照给定括号表达式指定的顺序去拆解矩阵乘法把每一次数值乘法的次数累加起来。我第一次刷到这道题时误以为是“矩阵连乘最小计算量”那种动态规划结果绕了一大圈。这篇文章就把题目的数学基础、完整解法、可运行代码以及我在实际做题过程中踩过的坑一次性讲透适合正在准备华为机考、或者想系统练栈和表达式模拟的人参考。1. 题目到底在考什么从一道华为机考真题说起1.1 题干还原与输入输出规则华为机考中矩阵乘法计算量估算的题干通常是这样描述的给定 n 个矩阵依次给出每个矩阵的行数和列数再给出一个只包含大写字母、左括号、右括号的表达式其中每个大写字母对应一个矩阵。要求你按照表达式中括号指定的乘法顺序估算整个过程中一共发生了多少次乘法运算。注意题目说的是“估算”计算量不是真的要求你输出乘积矩阵。也就是说你只需要计算乘法次数这一个数字。我当时看到这个题干的第一反应是回去翻线性代数教材后来发现完全没必要。标准输入格式可以这样理解假设有 3 个矩阵输入如下3 50 10 10 20 20 5 (A(BC))第一行的 3 表示有 3 个矩阵下面三行分别是 A、B、C 的行数和列数最后一行是带括号的乘法表达式。要求输出一个整数这个样例对应的输出是 3500。为什么是 3500而不是其他数字后文会展开推导。机考的输入输出就是这种直白格式难点通常不在读写而在你能不能把表达式解析对。1.2 别被“矩阵乘法”四个字带偏很多第一次刷这道题的人包括我在内都会陷入同一个误区想先把矩阵乘法的完整计算过程复习一遍。实际上这里真正需要用到的数学结论只有一条两个矩阵 A(m×n) 和 B(n×p) 相乘时乘法次数是 m×n×p。一旦记住这个公式剩下的问题就变成“怎么按照括号顺序把一次次乘法算出来”。还有一个更容易跑偏的方向就是联想到经典的矩阵连乘问题试图用动态规划找最小计算量。请务必注意那道题是“给定若干矩阵求最优结合顺序”而华为机考这道题是“已经给定了一个括号表达式你只需要照着这个顺序算”。两者的难度和思路完全不同。这道题本质上是一道“表达式模拟题”不是优化题。想通这一点代码写起来就会顺利很多。1.3 为什么值得专门总结这类题目在机考中出现的频率不低因为它能把几个基础能力放在一起考字符串遍历、括号匹配、栈的使用、以及对计算量的直观理解。实际工程里估算矩阵乘法计算量也有真实价值比如神经网络推理时调整张量运算的顺序、数据库查询计划里估算连接代价都是类似“先估算成本再决定执行方式”的思路。题目用一个很简单的场景把这些概念包装起来非常适合作为机考热身题。2. 计算量估算的核心公式、括号和栈2.1 一次矩阵乘法的成本m×n×p先说清楚为什么单次矩阵乘法的计算量是 m×n×p。假设 A 是 m 行 n 列的矩阵B 是 n 行 p 列的矩阵它们的乘积 C 是 m 行 p 列。C 中每一个元素等于 A 的某一行与 B 的某一列做点积点积需要 n 次乘法和 n-1 次加法。题目只统计乘法次数所以一个元素算 n 次乘法。C 共有 m×p 个元素因此总乘法次数就是 m×n×p。可以用一个生活化的类比帮助记忆你现在要生产 m×p 种产品每一种产品都需要从 n 个供应商那里分别取一个零件那么采购的零件总数就是 m×n×p。这个类比虽然粗糙但能帮助快速记住公式。还有一个容易被忽略的细节矩阵乘法的结果本身也有行列数结果是 m 行 p 列。因此当一次子表达式算完以后可以把结果矩阵当成一个新的矩阵继续参与后续计算。这也是后面用栈保存“当前矩阵尺寸”的理论基础。2.2 同样的表达式括号顺序不同计算量差多少沿着上面的公式可以把样例算一遍。A 是 50×10B 是 10×20C 是 20×5。表达式为(A(BC))意思是先算括号里的(BC)再用 A 去乘结果。先看(BC)B 是 10×20C 是 20×5乘法次数是 10×20×5 1000结果矩阵是 10×5。接着算A * (BC)A 是 50×10结果矩阵是 10×5乘法次数是 50×10×5 2500。总计算量是 1000 2500 3500。如果换一种结合顺序表达式变成((AB)C)计算量就会完全不同。先算(AB)A 是 50×10B 是 10×20乘法次数是 50×10×20 10000结果矩阵是 50×20。再算这个结果乘以 C50×20×5 5000。总计算量是 10000 5000 15000。同一个表达式仅仅括号位置不同计算量从 3500 变成 15000差了四倍多。这就是为什么在真实计算中合理安排矩阵乘法的顺序能带来巨大的性能差异也是这道题叫“计算量估算”的原因。2.3 为什么栈天然适合处理带括号的表达式现在需要关注的是怎么用程序照着表达式规定的顺序计算。带括号的表达式的特点在于遇到右括号时最近的一个括号范围内的运算必须立刻完成。这恰好符合栈的“后进先出”特性。遍历表达式时遇到矩阵字母就把它的尺寸压入栈遇到左括号不做处理遇到右括号就把栈顶最近的两个矩阵弹出做一次乘法计算再把合并后的结果尺寸压回栈。整个过程可以看成是一条指令流右括号就是“弹出两个元素做乘法再压回结果”的触发指令。为什么不直接用递归递归当然也能解决它的本质是使用函数调用栈原理上是一致的。但手动维护一个栈在机考里更直观也不会遇到递归深度的问题。我后来还发现这种“遇到结束符就弹栈合并”的模式和逆波兰表达式求值、括号匹配、简易计算器都属于同一类题学会一道往往能带动好几道类似题目。3. 完整实现从输入解析到两种代码写法3.1 读入数据并做好字母到矩阵维度的映射动手写代码前先想清楚数据怎么组织。输入的第一行是矩阵个数 n接下来 n 行按顺序给出 A、B、C 等矩阵的行列数。最方便的方式是用一个字典把大写字母映射成(行, 列)元组。这样遍历表达式时遇到字母就可以直接查到对应的尺寸。我在本地写了一个支持多组输入到文件结束的版本用sys.stdin.read()一次性读入所有内容再按顺序取数据。这样在牛客这类在线评测平台上即使题目隐藏了多组测试用例也能稳妥通过。import sys def solve(): data sys.stdin.read().split() if not data: return idx 0 output [] while idx len(data): n int(data[idx]) idx 1 dim {} for i in range(n): r int(data[idx]) c int(data[idx 1]) idx 2 dim[chr(ord(A) i)] (r, c) expr data[idx] idx 1 stack [] total 0 for ch in expr: if ch (: continue elif ch ): right_r, right_c stack.pop() left_r, left_c stack.pop() if left_c ! right_r: return total left_r * left_c * right_c stack.append((left_r, right_c)) else: stack.append(dim[ch]) output.append(str(total)) sys.stdout.write(\n.join(output)) if __name__ __main__: solve()这段代码有几个关键点。首先是字母映射chr(ord(A) i)把索引 i 转成对应的大写字母这样 A 对应第一组行列数B 对应第二组依此类推。其次是栈中保存的永远是矩阵尺寸元组不保存别的信息。最后是乘法次数累加这里一定要用大范围数据类型Python 的 int 是任意精度的但如果用 C 或者 Java就要特别注意使用 long 或 long long。3.2 手工推演一遍核心弹栈过程光看代码可能不够直观我把(A(BC))的完整处理过程做成一张表对照着看会清楚很多。当前字符操作栈内容累计乘法次数(忽略空0AA 入栈[(50,10)]0(忽略[(50,10)]0BB 入栈[(50,10),(10,20)]0CC 入栈[(50,10),(10,20),(20,5)]0)弹出 C 作为右矩阵、B 作为左矩阵计算 10×20×51000压入合并结果 (10,5)[(50,10),(10,5)]1000)弹出 (10,5) 作为右矩阵、A 作为左矩阵计算 50×10×52500压入合并结果 (50,5)[(50,5)]3500表格里最关键的一步是弹出顺序。第一次遇到右括号时栈中从底部到顶部依次是 A、B、C先弹出的是 C再弹出的是 B。C 是右操作数B 是左操作数。第二次遇到右括号时栈中从底部到顶部依次是 A 和合并后的(10,5)先弹出的是(10,5)也就是右操作数再弹出 A。最终栈里剩下(50,5)正好是 A 乘以(BC)的结果矩阵尺寸累计乘法次数 3500和题目输出一致。3.3 递归解法用函数调用栈代替手动栈除了手动栈递归也是一个很自然的思路。递归函数可以从表达式的某个位置开始解析如果当前位置是字母就返回这个矩阵的尺寸和累计代价如果当前位置是左括号就递归解析第一个子表达式再解析第二个子表达式两个子表达式分别作为左矩阵和右矩阵计算一次乘法后合并最后跳过右括号返回。这里给出一个简洁的递归版本核心逻辑如下def parse(expr, pos, dim): if expr[pos] (: left, pos, left_cost parse(expr, pos 1, dim) right, pos, right_cost parse(expr, pos 1, dim) if left[1] ! right[0]: raise ValueError(dimension mismatch) cost left_cost right_cost left[0] * left[1] * right[1] return (left[0], right[1]), pos 1, cost else: return dim[expr[pos]], pos 1, 0这段代码的返回结果是一个三元组合并后的矩阵尺寸、当前解析到的位置、以及该子表达式累计的乘法次数。递归在处理嵌套括号时确实很优雅代码量也少。但要注意如果括号嵌套非常深默认递归深度可能会不够。机考的用例一般不会极端到这个程度手动栈的实现会更加保险。3.4 复杂度分析与多组输入细节从时间复杂度来看无论是栈版本还是递归版本每个字符最多被处理常数次所以整体复杂度是 O(N)N 是表达式的长度。空间复杂度主要取决于栈中最多同时存在多少个矩阵尺寸最坏情况下约为 O(n)。这样的复杂度在机考中是完全没有压力的。多组输入是一个容易被忽略的点。有些题目描述里写“可能包含多组测试数据”此时用sys.stdin.read()统一读取后再通过 while 循环处理外部多个案例可以省去很多麻烦。我测试过把多组输入放在同一个文件里用上面的完整代码可以直接跑出多行结果非常适合在线评测。如果表达式字符串内部没有空格那么data[idx]取到的就是完整的表达式不会因为括号和字母连在一起而被拆散。4. 实战中容易踩的坑与排查手册4.1 弹栈顺序错误最常见的致命伤这道题最容易错的地方是弹栈顺序。栈的特点是后进先出遇到右括号时先弹出的一定是右边那个矩阵再弹出的是左边那个矩阵。很多初学者写成先弹出的当左矩阵后弹出的当右矩阵一旦表达式稍复杂结果就完全不对。我有一次在本地调试一个嵌套表达式怎么算都和答案对不上最后发现就是两个pop()的顺序反了。排查方法很简单构造一个最小场景(AB)。假设 A 是 m×nB 是 n×p正确答案应该是 m×n×p。如果程序输出结果不对优先检查弹栈和合并的逻辑。把这个最小用例跑通再跑复杂用例就有信心了。4.2 乘法次数用 int 存储数据一大就翻车另一个非常实际的问题是数据类型。矩阵的行数和列数可能都在 1000 左右单次乘法 1000×1000×1000 就是 10^9已经接近 int 类型的上限。如果整个表达式有多层嵌套多次累加后很容易超过 2^31-1用 int 存储必然溢出。数据类型大概范围推荐程度int-2147483648 ~ 2147483647不推荐long long约 -9e18 ~ 9e18推荐Python int任意精度不需要特别处理在 C 或 Java 中请记得所有参与乘法计算的变量都使用 long long 或 long。Python 虽然不用太担心溢出但也要注意不要在累加过程中把数值转换成浮点数否则精度会出问题。4.3 维度不匹配和非法表达式要不要处理题目通常会保证输入的表达式合法也就是左矩阵的列数一定等于右矩阵的行数但我在写代码时还是习惯加一个校验。比如当left_c ! right_r时说明两个矩阵根本不能相乘这时候程序应该停止计算而不是继续输出一个错误的值。这样的校验在正常测试里永远不会触发但万一遇到手滑构造的错误数据能避免浪费大量调试时间。还有一个和读取相关的坑如果表达式里混入了空格或换行比如(A (B C))直接遍历会出错。稳妥的做法是在读入时用split()处理这样表达式整体会变成一个干净的字符串。如果题目给出的表达式实在太复杂甚至包含小写字母或数字可以先过滤掉非字母非括号字符不过以华为机考原题的设定这种情况基本不会出现。4.4 变体题目与延伸方向这道题的几个常见变形可以帮助你加深理解。第一种变形是不给括号要求按从左到右的顺序计算。这时栈版本不会主动触发计算需要在遍历完表达式后把栈中所有矩阵按顺序乘一遍逻辑上就变成了另一种模拟。第二种变形是要求输出最终结果矩阵的行数和列数那么栈中最后剩下的那个元组就是答案代码改动非常小。更值得警惕的变形是“求最小计算量”例如给你几个矩阵的维度不指定括号顺序让你求最少需要的乘法次数。那就是经典的矩阵连乘问题需要用区间动态规划而不是简单模拟。理解这两者的区别是机考中不掉坑的关键。做这道题时只要时刻记住“题目让我按指定顺序算不是让我找最优顺序”思路就不会跑偏。5. 从这道题看华为机考的刷题套路5.1 栈模拟题的通用思考框架矩阵乘法计算量估算不是孤立的题目它代表了一类“栈模拟题”。这类题的通用思考框架可以总结成四步先把输入元素抽象成栈里的元素比如把矩阵尺寸作为栈元素然后找到触发计算的事件在本题里就是右括号接着定义合并规则也就是弹出两个元素、计算代价、压回结果最后维护一个统计变量记录所有中间过程的累计结果。这个框架可以直接迁移到括号匹配、逆波兰表达式求值、简易计算器等问题。华为机考里中低难度的算法题相当一部分属于这种类型与其盲目刷一百道散题不如先把这一类栈模拟题集中刷透。我当时就是花了一个下午把四五道同类题目放在一起做后面再碰到表达式相关的题基本一眼就知道怎么入手。5.2 机考现场的三个自测动作写完代码后不要急着提交先完成三个自测动作。第一跑题目的样例确保能输出 3500 这类标准答案。第二跑一个两矩阵的最小用例(AB)用手算出结果后对拍这样可以快速验证弹栈顺序是否正确。第三跑一个多层嵌套表达式比如(A(B(CD)))确认多层括号下的索引和累计逻辑不会出错。如果用的是 Python建议把测试用例保存到文本文件里然后用重定向的方式运行比如python main.py input.txt这样能避免反复粘贴输入浪费时间。我实际刷题时吃过不少“样例能过提交失败”的亏后来养成了这个自测习惯提交通过率明显提升。我自己在这道题里最大的收获是发现机考重点考察的往往不是高深算法而是你能不能把一个实际场景抽象成合适的数据结构并且把边界情况想清楚。矩阵乘法计算量估算看起来不难可弹栈顺序、数据类型、多组输入这些细节点每一个都能让代码翻车。建议大家在考前把同类栈模拟题集中做两三道找到手感和踩坑的敏感度。最后再分享一个小技巧不管题目样例多简单都先用(AB)这种最小场景验证一遍它能用最短时间暴露你八成以上的逻辑错误。 
长河君 · 2026/10/1 6:19:50 · 阅读 1.2k 矩阵乘法计算量估算：栈模拟与表达式解析实战解析
刷华为机考的同学应该对“矩阵乘法计算量估算”这道题不陌生。题目名字听起来像线性代数应用题真正上手才发现它考的是字符串解析和栈模拟核心是让你按照给定括号表达式指定的顺序去拆解矩阵乘法把每一次数值乘法的次数累加起来。我第一次刷到这道题时误以为是“矩阵连乘最小计算量”那种动态规划结果绕了一大圈。这篇文章就把题目的数学基础、完整解法、可运行代码以及我在实际做题过程中踩过的坑一次性讲透适合正在准备华为机考、或者想系统练栈和表达式模拟的人参考。1. 题目到底在考什么从一道华为机考真题说起1.1 题干还原与输入输出规则华为机考中矩阵乘法计算量估算的题干通常是这样描述的给定 n 个矩阵依次给出每个矩阵的行数和列数再给出一个只包含大写字母、左括号、右括号的表达式其中每个大写字母对应一个矩阵。要求你按照表达式中括号指定的乘法顺序估算整个过程中一共发生了多少次乘法运算。注意题目说的是“估算”计算量不是真的要求你输出乘积矩阵。也就是说你只需要计算乘法次数这一个数字。我当时看到这个题干的第一反应是回去翻线性代数教材后来发现完全没必要。标准输入格式可以这样理解假设有 3 个矩阵输入如下3 50 10 10 20 20 5 (A(BC))第一行的 3 表示有 3 个矩阵下面三行分别是 A、B、C 的行数和列数最后一行是带括号的乘法表达式。要求输出一个整数这个样例对应的输出是 3500。为什么是 3500而不是其他数字后文会展开推导。机考的输入输出就是这种直白格式难点通常不在读写而在你能不能把表达式解析对。1.2 别被“矩阵乘法”四个字带偏很多第一次刷这道题的人包括我在内都会陷入同一个误区想先把矩阵乘法的完整计算过程复习一遍。实际上这里真正需要用到的数学结论只有一条两个矩阵 A(m×n) 和 B(n×p) 相乘时乘法次数是 m×n×p。一旦记住这个公式剩下的问题就变成“怎么按照括号顺序把一次次乘法算出来”。还有一个更容易跑偏的方向就是联想到经典的矩阵连乘问题试图用动态规划找最小计算量。请务必注意那道题是“给定若干矩阵求最优结合顺序”而华为机考这道题是“已经给定了一个括号表达式你只需要照着这个顺序算”。两者的难度和思路完全不同。这道题本质上是一道“表达式模拟题”不是优化题。想通这一点代码写起来就会顺利很多。1.3 为什么值得专门总结这类题目在机考中出现的频率不低因为它能把几个基础能力放在一起考字符串遍历、括号匹配、栈的使用、以及对计算量的直观理解。实际工程里估算矩阵乘法计算量也有真实价值比如神经网络推理时调整张量运算的顺序、数据库查询计划里估算连接代价都是类似“先估算成本再决定执行方式”的思路。题目用一个很简单的场景把这些概念包装起来非常适合作为机考热身题。2. 计算量估算的核心公式、括号和栈2.1 一次矩阵乘法的成本m×n×p先说清楚为什么单次矩阵乘法的计算量是 m×n×p。假设 A 是 m 行 n 列的矩阵B 是 n 行 p 列的矩阵它们的乘积 C 是 m 行 p 列。C 中每一个元素等于 A 的某一行与 B 的某一列做点积点积需要 n 次乘法和 n-1 次加法。题目只统计乘法次数所以一个元素算 n 次乘法。C 共有 m×p 个元素因此总乘法次数就是 m×n×p。可以用一个生活化的类比帮助记忆你现在要生产 m×p 种产品每一种产品都需要从 n 个供应商那里分别取一个零件那么采购的零件总数就是 m×n×p。这个类比虽然粗糙但能帮助快速记住公式。还有一个容易被忽略的细节矩阵乘法的结果本身也有行列数结果是 m 行 p 列。因此当一次子表达式算完以后可以把结果矩阵当成一个新的矩阵继续参与后续计算。这也是后面用栈保存“当前矩阵尺寸”的理论基础。2.2 同样的表达式括号顺序不同计算量差多少沿着上面的公式可以把样例算一遍。A 是 50×10B 是 10×20C 是 20×5。表达式为(A(BC))意思是先算括号里的(BC)再用 A 去乘结果。先看(BC)B 是 10×20C 是 20×5乘法次数是 10×20×5 1000结果矩阵是 10×5。接着算A * (BC)A 是 50×10结果矩阵是 10×5乘法次数是 50×10×5 2500。总计算量是 1000 2500 3500。如果换一种结合顺序表达式变成((AB)C)计算量就会完全不同。先算(AB)A 是 50×10B 是 10×20乘法次数是 50×10×20 10000结果矩阵是 50×20。再算这个结果乘以 C50×20×5 5000。总计算量是 10000 5000 15000。同一个表达式仅仅括号位置不同计算量从 3500 变成 15000差了四倍多。这就是为什么在真实计算中合理安排矩阵乘法的顺序能带来巨大的性能差异也是这道题叫“计算量估算”的原因。2.3 为什么栈天然适合处理带括号的表达式现在需要关注的是怎么用程序照着表达式规定的顺序计算。带括号的表达式的特点在于遇到右括号时最近的一个括号范围内的运算必须立刻完成。这恰好符合栈的“后进先出”特性。遍历表达式时遇到矩阵字母就把它的尺寸压入栈遇到左括号不做处理遇到右括号就把栈顶最近的两个矩阵弹出做一次乘法计算再把合并后的结果尺寸压回栈。整个过程可以看成是一条指令流右括号就是“弹出两个元素做乘法再压回结果”的触发指令。为什么不直接用递归递归当然也能解决它的本质是使用函数调用栈原理上是一致的。但手动维护一个栈在机考里更直观也不会遇到递归深度的问题。我后来还发现这种“遇到结束符就弹栈合并”的模式和逆波兰表达式求值、括号匹配、简易计算器都属于同一类题学会一道往往能带动好几道类似题目。3. 完整实现从输入解析到两种代码写法3.1 读入数据并做好字母到矩阵维度的映射动手写代码前先想清楚数据怎么组织。输入的第一行是矩阵个数 n接下来 n 行按顺序给出 A、B、C 等矩阵的行列数。最方便的方式是用一个字典把大写字母映射成(行, 列)元组。这样遍历表达式时遇到字母就可以直接查到对应的尺寸。我在本地写了一个支持多组输入到文件结束的版本用sys.stdin.read()一次性读入所有内容再按顺序取数据。这样在牛客这类在线评测平台上即使题目隐藏了多组测试用例也能稳妥通过。import sys def solve(): data sys.stdin.read().split() if not data: return idx 0 output [] while idx len(data): n int(data[idx]) idx 1 dim {} for i in range(n): r int(data[idx]) c int(data[idx 1]) idx 2 dim[chr(ord(A) i)] (r, c) expr data[idx] idx 1 stack [] total 0 for ch in expr: if ch (: continue elif ch ): right_r, right_c stack.pop() left_r, left_c stack.pop() if left_c ! right_r: return total left_r * left_c * right_c stack.append((left_r, right_c)) else: stack.append(dim[ch]) output.append(str(total)) sys.stdout.write(\n.join(output)) if __name__ __main__: solve()这段代码有几个关键点。首先是字母映射chr(ord(A) i)把索引 i 转成对应的大写字母这样 A 对应第一组行列数B 对应第二组依此类推。其次是栈中保存的永远是矩阵尺寸元组不保存别的信息。最后是乘法次数累加这里一定要用大范围数据类型Python 的 int 是任意精度的但如果用 C 或者 Java就要特别注意使用 long 或 long long。3.2 手工推演一遍核心弹栈过程光看代码可能不够直观我把(A(BC))的完整处理过程做成一张表对照着看会清楚很多。当前字符操作栈内容累计乘法次数(忽略空0AA 入栈[(50,10)]0(忽略[(50,10)]0BB 入栈[(50,10),(10,20)]0CC 入栈[(50,10),(10,20),(20,5)]0)弹出 C 作为右矩阵、B 作为左矩阵计算 10×20×51000压入合并结果 (10,5)[(50,10),(10,5)]1000)弹出 (10,5) 作为右矩阵、A 作为左矩阵计算 50×10×52500压入合并结果 (50,5)[(50,5)]3500表格里最关键的一步是弹出顺序。第一次遇到右括号时栈中从底部到顶部依次是 A、B、C先弹出的是 C再弹出的是 B。C 是右操作数B 是左操作数。第二次遇到右括号时栈中从底部到顶部依次是 A 和合并后的(10,5)先弹出的是(10,5)也就是右操作数再弹出 A。最终栈里剩下(50,5)正好是 A 乘以(BC)的结果矩阵尺寸累计乘法次数 3500和题目输出一致。3.3 递归解法用函数调用栈代替手动栈除了手动栈递归也是一个很自然的思路。递归函数可以从表达式的某个位置开始解析如果当前位置是字母就返回这个矩阵的尺寸和累计代价如果当前位置是左括号就递归解析第一个子表达式再解析第二个子表达式两个子表达式分别作为左矩阵和右矩阵计算一次乘法后合并最后跳过右括号返回。这里给出一个简洁的递归版本核心逻辑如下def parse(expr, pos, dim): if expr[pos] (: left, pos, left_cost parse(expr, pos 1, dim) right, pos, right_cost parse(expr, pos 1, dim) if left[1] ! right[0]: raise ValueError(dimension mismatch) cost left_cost right_cost left[0] * left[1] * right[1] return (left[0], right[1]), pos 1, cost else: return dim[expr[pos]], pos 1, 0这段代码的返回结果是一个三元组合并后的矩阵尺寸、当前解析到的位置、以及该子表达式累计的乘法次数。递归在处理嵌套括号时确实很优雅代码量也少。但要注意如果括号嵌套非常深默认递归深度可能会不够。机考的用例一般不会极端到这个程度手动栈的实现会更加保险。3.4 复杂度分析与多组输入细节从时间复杂度来看无论是栈版本还是递归版本每个字符最多被处理常数次所以整体复杂度是 O(N)N 是表达式的长度。空间复杂度主要取决于栈中最多同时存在多少个矩阵尺寸最坏情况下约为 O(n)。这样的复杂度在机考中是完全没有压力的。多组输入是一个容易被忽略的点。有些题目描述里写“可能包含多组测试数据”此时用sys.stdin.read()统一读取后再通过 while 循环处理外部多个案例可以省去很多麻烦。我测试过把多组输入放在同一个文件里用上面的完整代码可以直接跑出多行结果非常适合在线评测。如果表达式字符串内部没有空格那么data[idx]取到的就是完整的表达式不会因为括号和字母连在一起而被拆散。4. 实战中容易踩的坑与排查手册4.1 弹栈顺序错误最常见的致命伤这道题最容易错的地方是弹栈顺序。栈的特点是后进先出遇到右括号时先弹出的一定是右边那个矩阵再弹出的是左边那个矩阵。很多初学者写成先弹出的当左矩阵后弹出的当右矩阵一旦表达式稍复杂结果就完全不对。我有一次在本地调试一个嵌套表达式怎么算都和答案对不上最后发现就是两个pop()的顺序反了。排查方法很简单构造一个最小场景(AB)。假设 A 是 m×nB 是 n×p正确答案应该是 m×n×p。如果程序输出结果不对优先检查弹栈和合并的逻辑。把这个最小用例跑通再跑复杂用例就有信心了。4.2 乘法次数用 int 存储数据一大就翻车另一个非常实际的问题是数据类型。矩阵的行数和列数可能都在 1000 左右单次乘法 1000×1000×1000 就是 10^9已经接近 int 类型的上限。如果整个表达式有多层嵌套多次累加后很容易超过 2^31-1用 int 存储必然溢出。数据类型大概范围推荐程度int-2147483648 ~ 2147483647不推荐long long约 -9e18 ~ 9e18推荐Python int任意精度不需要特别处理在 C 或 Java 中请记得所有参与乘法计算的变量都使用 long long 或 long。Python 虽然不用太担心溢出但也要注意不要在累加过程中把数值转换成浮点数否则精度会出问题。4.3 维度不匹配和非法表达式要不要处理题目通常会保证输入的表达式合法也就是左矩阵的列数一定等于右矩阵的行数但我在写代码时还是习惯加一个校验。比如当left_c ! right_r时说明两个矩阵根本不能相乘这时候程序应该停止计算而不是继续输出一个错误的值。这样的校验在正常测试里永远不会触发但万一遇到手滑构造的错误数据能避免浪费大量调试时间。还有一个和读取相关的坑如果表达式里混入了空格或换行比如(A (B C))直接遍历会出错。稳妥的做法是在读入时用split()处理这样表达式整体会变成一个干净的字符串。如果题目给出的表达式实在太复杂甚至包含小写字母或数字可以先过滤掉非字母非括号字符不过以华为机考原题的设定这种情况基本不会出现。4.4 变体题目与延伸方向这道题的几个常见变形可以帮助你加深理解。第一种变形是不给括号要求按从左到右的顺序计算。这时栈版本不会主动触发计算需要在遍历完表达式后把栈中所有矩阵按顺序乘一遍逻辑上就变成了另一种模拟。第二种变形是要求输出最终结果矩阵的行数和列数那么栈中最后剩下的那个元组就是答案代码改动非常小。更值得警惕的变形是“求最小计算量”例如给你几个矩阵的维度不指定括号顺序让你求最少需要的乘法次数。那就是经典的矩阵连乘问题需要用区间动态规划而不是简单模拟。理解这两者的区别是机考中不掉坑的关键。做这道题时只要时刻记住“题目让我按指定顺序算不是让我找最优顺序”思路就不会跑偏。5. 从这道题看华为机考的刷题套路5.1 栈模拟题的通用思考框架矩阵乘法计算量估算不是孤立的题目它代表了一类“栈模拟题”。这类题的通用思考框架可以总结成四步先把输入元素抽象成栈里的元素比如把矩阵尺寸作为栈元素然后找到触发计算的事件在本题里就是右括号接着定义合并规则也就是弹出两个元素、计算代价、压回结果最后维护一个统计变量记录所有中间过程的累计结果。这个框架可以直接迁移到括号匹配、逆波兰表达式求值、简易计算器等问题。华为机考里中低难度的算法题相当一部分属于这种类型与其盲目刷一百道散题不如先把这一类栈模拟题集中刷透。我当时就是花了一个下午把四五道同类题目放在一起做后面再碰到表达式相关的题基本一眼就知道怎么入手。5.2 机考现场的三个自测动作写完代码后不要急着提交先完成三个自测动作。第一跑题目的样例确保能输出 3500 这类标准答案。第二跑一个两矩阵的最小用例(AB)用手算出结果后对拍这样可以快速验证弹栈顺序是否正确。第三跑一个多层嵌套表达式比如(A(B(CD)))确认多层括号下的索引和累计逻辑不会出错。如果用的是 Python建议把测试用例保存到文本文件里然后用重定向的方式运行比如python main.py input.txt这样能避免反复粘贴输入浪费时间。我实际刷题时吃过不少“样例能过提交失败”的亏后来养成了这个自测习惯提交通过率明显提升。我自己在这道题里最大的收获是发现机考重点考察的往往不是高深算法而是你能不能把一个实际场景抽象成合适的数据结构并且把边界情况想清楚。矩阵乘法计算量估算看起来不难可弹栈顺序、数据类型、多组输入这些细节点每一个都能让代码翻车。建议大家在考前把同类栈模拟题集中做两三道找到手感和踩坑的敏感度。最后再分享一个小技巧不管题目样例多简单都先用(AB)这种最小场景验证一遍它能用最短时间暴露你八成以上的逻辑错误。