P2607. 火星文计算2

解题思路

这是一个非常典型的中缀表达式求值类的问题，类似于 基本计算器、经典题型. 基本计算器II。

对于这类表达式求值相关的栈题，我们通常需要考虑以下问题：

• 遇到数字应该如何处理？
• 遇到运算符应该如何处理？
• 何时进行入栈？
• 何时进行出栈以及运算操作？
• 退出循环后如何处理栈中内容？

问题1：遇到数字应该如何处理？

数字显然应该暂存在栈中，等待后续出栈进行运算。 由于需要处理数字不止一位数的情况，我们可以通过构建一个初始值为 0 的变量 num，通过 num = num * 10 + int(ch) 的方式来更新数字。 这个技巧在很多类似题目都多次出现。

问题2：遇到运算符应该如何处理？

题目告知，两种运算符中，`#` 的优先级高于 `$`。 思考小学数学的四则运算，*** 的优先级高于 +**。 我们在做数学四则运算的时候，总是会先处理乘除，再处理加减。

如果这道题的 # 是 *，$ 是 +，那么我们可以这样处理： 遇到 + 直接跳过（符号不入栈），把所有 * 运算处理完毕后，将栈中的所有元素进行求和即可。 （因为除了 *，剩下的 +，可以直接求和）

因此这道题也是类似，我们必须把 `#` 都处理了，再处理 `$`。 遇到 $ 直接跳过（符号不入栈），把所有 # 运算处理完毕后，再考虑最终的栈中情况（问题5）。

问题3：何时进行入栈操作？

在前一点中其实已经提到，遇到符号的时候是不进行入栈的。 但是，遇到符号的时候意味着一个数字已经完全取得了。 因此，数字的入栈时机是在遇到一个符号的时候，我们必须把之前得到的 num 入栈，同时重置数字 num = 0。

问题4：何时进行出栈以及运算操作？

出栈意味着运算。

考虑中缀表达式：

如果我们想要计算 12#34 的结果，其实是不能在遍历到 # 的时候来计算的，因为这个时候我们并不知道 # 后面紧跟着的数字是什么。 也不能在遍历到数字 3 或 4 的时候来做计算，因为此时我们并不知道这个数字的位数是多少，无法确定当前得到的数字 num 就是我们想要的数字。

因此，进行出栈和计算的时机，一定是当遍历到一个新的符号的时候，也就是遍历到 $ 的时候，才需要进行计算。

又结合上述的问题2，我们在第一次遍历的过程中，只需要计算 #，所以我们可以使用一个布尔型变量 pre_sign_well 来标记上一个运算符是否为 #。 该变量初始化为 False，表示在遇到第一个数字的时候，肯定是不用进行出栈操作和运算的。

只有在遇到一个运算符，且发现上一个运算符是 `#` 的时候，也就是 pre_sign_well = True 的时候，才需要进行出栈和运算，且需要把运算结果重新压回栈中。 然后我们还需要根据新遇到的运算符，修改 pre_sign_well 的值。

另外根据问题3和4，原式子中的最后一个字符是数字，如果想要正确地取出最后一个数字并进行运算，我们可以在原式子末尾增加一个非数字字符，或者在循环过程中判断是否已经遍历到最后一个字符。

问题5：退出循环后如何处理栈中内容？

退出循环后，原式子中的所有 # 运算符都已经处理完毕，栈中剩余元素都需要进行 `$` 运算。 和简单的 + 不同，我们不能够直接求和，我们再次对栈中所有元素进行循环，依次进行 $ 运算即可。

复杂度分析 设表达式字符串的长度为 n。主循环对补了一个空格哨兵的 s 做单次遍历：遇到数字用 num = num * 10 + int(ch) 累积，O(1)；遇到非数字字符（# 、$ 或收尾空格）把攒好的数字入栈，若前一个符号是 #（pre_sign_well 为真）则弹出两个数做一次 cal_well 计算并把结果压回，都是栈顶的常数次操作。每个数字至多入栈一次、至多参与一次 # 运算，所以主循环总代价 O(n)。退出循环后，栈中剩余 k 个元素（k 不超过数字个数）再从左到右做一遍 $ 运算，代价 O(k)，不超过 O(n)。整体时间复杂度 O(n)，瓶颈就是这一遍线性扫描；空间复杂度 O(n)，最坏情况（运算符全是 $）所有数字都会留在栈中等待收尾计算。

边界与注意事项

• 代码在 s 末尾补了一个空格（s += " "）作哨兵：入栈和结算都发生在「遇到非数字字符」的时刻，不补哨兵的话最后一个数字永远没有机会入栈参与运算，这是本实现最关键的细节。
• 「# 优先级高于 $」的落实方式：遇到符号时符号本身不入栈，只有 pre_sign_well 标记表明上一个符号是 # 时才当场结算，保证所有 # 先算完；剩余的 $ 在收尾循环里从左到右依次计算，正好满足题面「相同运算符按从左到右顺序运算」的规则。
• 输入只有一个数字、没有任何运算符时也能正确工作：该数字在哨兵空格处入栈，收尾循环的 stack[1:] 为空，直接输出 stack[0] 即数字本身。
• 题面约定 x、y 均为无符号整数，代码据此只用 isdigit 识别数字、不处理负号；多位数依靠 num * 10 + int(ch) 累积，不受位数限制。