含二元与一元节点的RPN树高度计算及不完整表达式最小完成深度咨询

一、完整RPN表达式的树深度计算 #

用栈模拟计算过程，栈中每个元素记录对应子树的深度，规则如下：

• 遇到叶子节点x：把深度值1压入栈
• 遇到一元运算符cos/exp：弹出栈顶的深度值d，新子树深度为d + 1，将该值压回栈
• 遇到二元运算符+/-/*：弹出栈顶两个深度值d1和d2，新子树深度为max(d1, d2) + 1，将该值压回栈

遍历完所有token后，栈里剩下的唯一数值就是整个RPN树的深度。

示例 #

• 纯二元极端场景：x x + x +
  计算过程：[1] → [1,1] → [2] → [2,1] → [3]，最终深度为3
• 纯一元极端场景：x cos exp cos
  计算过程：[1] → [2] → [3] → [4]，最终深度为4
• 混合场景：x cos x +
  计算过程：[1] → [2] → [2,1] → [3]，最终深度为3

二、不完整RPN表达式的最小完成深度 #

这里的“不完整”指当前表达式无法构成完整树（栈长度k ≥ 2），需添加节点让栈最终只剩1个元素。要得到最小的完成深度，最优策略是：

1. 只添加二元运算符（别加叶子或一元运算符——加叶子会增加栈长度，需要更多合并操作；加一元会拉高子树深度，都会让最终深度变大）
2. 每次优先合并栈中深度最小的两个子树：弹出两个最小深度d_min1和d_min2，合并后的深度为max(d_min1, d_min2) + 1，把这个值压回栈
3. 重复步骤2，直到栈长度变为1，此时栈中的值就是最小完成深度

示例 #

假设当前不完整表达式对应的栈是[3,1,2]：

• 第一步：合并最小的1和2，得到max(1,2)+1=3，栈变为[3,3]
• 第二步：合并两个3，得到max(3,3)+1=4，最终最小完成深度为4

内容的提问来源于stack exchange，提问作者Edward Finkelstein