P3005. 提取字符串中最长数学表达式

解题思路

本题的难点其实在于如何提取出最长合法数学表达式，而不是最终的运算。 运算这一步可以直接使用 `eval()` 内置函数来完成，也可以正常地使用 栈 来进行表达式求值。

因为提取这一步本身已经比较复杂了，所以在得到最长合法数学表达式之后，求值使用 eval() 直接得到结果并没有太大问题。

提取合法表达式

什么是合法表达式

关于合法表达式的判断，题目其实并没有过多详细说明。 除了最基本的不能包括字母或其他字符，不能出现连续的操作符等等，我们需要特别注意以下情况：

• 单个数字属于合法表达式
• "+" 和 "-" 是可以作为符号出现在表达式的首位的，但是 **"*" 不行**
• 除了数字 0 以外，表达式中的任何一个数字都不能出现 先导 0
• 表达式的最后一位必须是数字，而不能是操作数

举一些例子就明白了。譬如：

• "123"、"0"、"-123"、"-0"、"+123"、"+0" 是合法表达式
• "+1+2"、"-1*2+3" 是合法表达式，但是 "*1+2" 不是合法表达式
• "00"、"01"、"-00"、"-01"、"1-02" 不是合法表达式
• "+1+2+"、"1*2+3-" 不是合法表达式

因此，关于合法表达式的提取，需要进行非常多的分类讨论。

合法表达式双指针框架

我们可以使用两个指针 `i` 和 `j` 来进行合法表达式的提取。 其中，i 表示合法表达式的起始位置，j 表示合法表达式的终止位置。譬如：

对于任何一个合法表达式（无论是否最长），我们就能够使用 s[i:j] 来表示这个表达式。

显然区间 [i, j) 是一个 左闭右开区间，这样做的好处是，当考虑完一个合法表达式之后，我们都可以进一步地以 j 的位置作为新的 i，来考虑后续的新的表达式。

另外，由于 i 和 j 的修改条件相对复杂，很难使用 for 循环来完成，因此很容易想到关于 i 和 j 的前进都应该用 `while` 循环 来进行。

当 s[i] 是一个数字，或者 s[i] 是 "+" 或 "-" 的时候，i 可以作为一个合法表达式的起始位置。 在固定 s[i] 为首位的情况下，我们可以初始化 j = i，让 j 继续前进，寻找当前合法表达式的终止位置。 在结束关于 j 的循环之后，我们再重置 i = j，作为下一个合法表达式寻找的起始位置。

当然，如果作为起始位置的 s[i] 是其他无关字符（"*" 或其他字母等等），则 s[i] 不是一个合法的起始位置，直接令 i 前进递增即可。

综上所述，我们可以构建出整体的双指针框架为：

关于 j 的内层 while 循环的判断

关于 j 的内层循环，可以简单分为三种情况：

1. s[j] 是数字 2. s[j] 是操作符 "+-*" 3. s[j] 是其他无关字符

s[j] 是其他无关字符的情况

如果 s[j] 是其他无关字符，这种情况最为简单，说明当前 s[i:j] 就是一个无法继续延长的合法表达式，可以直接退出关于 j 的 while 循环。譬如：

故框架可以修改如下：

注意到，这里的 break 即表示退出循环时，j 所代表的终止位置必须表示开区间取不到的位置。 这一点在后续的讨论中非常重要，如果不注意这一点的话很容易使得最后取得的表达式长 1 位或短 1 位。

s[j] 是数字的情况

当 s[j] 是 1-9 之间的数字时，这种情况也是比较简单的。 此时不用考虑任何特殊情况，此时的 s[j] 一定是表达式中的一部分，直接进行 j 的递增，考虑下一个 j 即可。譬如：

对应的代码为：

当 s[j] 是 0 的时候，情况就变得复杂了。 因为可能存在非法先导 0，如果 s[j] 是一个非法先导 0 的话，那么此时表达式必须在 s[j+1] 的位置结束，应该令 j 递增 1 之后，退出循环。 譬如 "1+02"，那么应该取 "0" 之后的下一个字符 "2" 应该作为终止位置，提取出合法表达式 "1+0"。

非法先导 0 必须同时满足两个条件：

• 非法先导 0 的前一位必须是一个非数字（可以是操作符、也可以是其他无关字符），这意味着这个 0 并不是位于某个数字中其他位置。譬如，"101" 和 "110" 中的 0 就不是先导 0。
• 非法先导 0 的后一位必须是一个数字，这意味着这个 0 并非一个单独的 0（因为对于数字 0 而言，先导 0 是合法的），而是后面跟着数字。譬如，"1+0+1" 和 "1+1+0" 中的 0 就是合法的。

如果 s[j] 不是一个非法先导 0 的话，那么这个 0 的行为就可以其他数字的行为一致，直接递增即可。 因此，关于先导 0 的判断，我们可以进一步填充上述代码：

s[j] 是操作符的情况

当 s[j] 是一个操作符的时候，只有当 s[j] 的后面紧跟着一个数字时，这个表达式才能进一步延长。 否则，此时表达式必须在 s[j] 的位置结束，譬如 "1+2+"，我们要提取出合法表达式 "1+2"。即：

对应代码为：

将三种情况均讨论完毕后，关于 j 的 while 循环内的内容也就完成了。我们更新代码框架如下：

退出内层循环后的答案更新

再次重申，退出关于 j 的 while 循环后，此时的表达式为 s[i:j]，j 表示右开区间。

在关于 j 的 while 循环中，单个 "+" 或 "-" 并不会被认为是一个合法表达式。 譬如 "++1" 或 "+a1" 中的第一个 "+"，并不会被认为是一个合法表达式。 此时存在 i == j 成立，s[i:j] 是一个空串。

由于后续我们需要更新 i = j，重新以 j 作为一个新的表达式起始位置，如果此时不对 j 做任何修改，那么 i 会始终停留在当前位置，从而导致 死循环。 故如果出现 i == j 成立，我们必须强制令 j 前进一位。

剩下的就是答案更新了，由于题目要求找到最长合法表达式，我们可以使用两个全局变量 start_idx 和 end_idx 来储存全局的最长合法表达式的起始位置和终止位置。 初始化 start_idx 和 end_idx 相等（即它们做差为 0），当发现 j - i > start_idx - end_idx 的时候，我们将 start_idx 和 end_idx 分别修改为 j 和 i 即可。

这里的判断条件之所以是 j - i > end_idx - start_idx 而不是 j - i >= end_idx - start_idx，是因为题目要求当出现多个最长合法表达式时，选择第一个最长合法表达式。 > 可以保证，只有在找到更长的表达式的时候才进行更新。

如果题目要求当出现多个最长合法表达式时，选择最后一个最长合法表达式的话，那么应该使用 >=。 这样就可以在找到等长的最长表达式时，也进行更新了，最终结果一定是最后一个最长合法表达式。

在退出关于 i 的 while 循环之后，全局的 start_idx 和 end_idx 也更新完毕了。 sub_s = s[start_idx:end_idx] 就是在双指针循环中拿到的最长合法表达式。

如果 sub_s 是空串（即原字符串中不存在任何合法表达式），则直接输出 0。 否则直接调用内置函数 eval() 得到结果。

避免越界的技巧

在上述关于 j 的 while 循环中，我们的代码其实并没有讨论关于 j 的越界情况。 实际上在循环中是有可能出现越界的，因为我们在循环中多次取了 s[j-1] 和 s[j+1] 来进行判断。

但因为分类讨论的情况很多，比较复杂，如果反复地进行越界判断会使得代码可读性变得非常差，也不利于我们进行调试和修改。

在最终的代码中，我们用上了这样一个技巧：在循环开始之前，往原字符串 `s` 的前后均填充了一个不会影响最终结果的字符。

无论原来的 s 的最开头和最末尾是什么字符，新填充的两个无关字符必然不会被包含在表达式中，那么在关于 j 的 while 循环中，我们在取 s[j-1] 和 s[j+1] 的时候，必然不会出现越界，也不需要在 while 循环中写上繁琐的越界判断了。

栈模拟表达式求值

在提取出最长合法表达式之后，剩下的内容就比较常规了，使用 栈 来进行表达式求值的模拟。 对于使用 Python 的同学而言，这里可以直接用 eval() 内置函数得到结果，但其他语言的同学则需要手动实现 eval() 功能。

相关的题目包括 基本计算器、经典题型. 基本计算器 II、【栈】2023C-火星文计算2。

复杂度分析 设输入字符串长度为 n（代码在首尾各补了一个无关字符，长度变为 n + 2，不影响量级）。

• 提取阶段：外层 while 用 i 扫描表达式起点，内层 while 用 j 扫描表达式终点，看起来是两层循环，但关键在于内层循环结束后立即执行 i = j（或 i 自增），两个指针都只向前、从不回退，所以每个字符在全程中只被访问常数次，提取阶段整体为 O(n)。
• 求值阶段 cal()：对提取出的最长合法表达式做单遍扫描，遇到乘号即时弹栈相乘，最后把栈中元素求和；表达式长度不超过 n，为 O(n)。

总时间复杂度为 O(n)，空间复杂度为 O(n)，主要是求值用的栈以及截取出来的子串。