跳到主要内容

一个感叹号,和它假装不存在的那条空栈路径

阿舟
阿舟

· 阅读约 6 分钟

上个月底在 dev.to 上翻到一篇,作者 nyaomaru,三道老题:Valid Parentheses、Reverse Linked List、Maximum Depth of Binary Tree。标了 AI 辅助,配一个自己写的可视化工具 DSA View View,边跑边把状态摊开。他之前那篇 Two Sum、Binary Search、Bubble Sort 我也看过,一个路子。

点进去本来只想看看栈和递归他怎么画。结果让我停下来敲键盘的,是评论区一条回复。

先把代码贴出来。

const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
const stack: string[] = [];

for (const char of s) {
  if (char === '(' || char === '[' || char === '{') {
    stack.push(char);
  } else {
    if (stack.pop()! !== pairs[char]) return false;
  }
}
return stack.length === 0;

写法没毛病,教科书上的东西,不展开:闭括号来了必须 pop 而不是 peek,不管匹不匹配,栈顶那个开括号都得被消耗掉——匹配就顺手带走,不匹配就是撞南墙 return false。O(n) 时间,O(n) 空间,最坏情况整串全是开括号。

眼睛要盯的是 pop() 后面那个 !

Nazar Boyko 在评论区说的那句话,翻译过来就一层意思:这个非空断言,把空栈那条路径盖住了。比如输入 )(,它照样给出正确答案——可那条路径在运行时是真会走到的。

我在屏幕前点了点头,然后又点了一遍。

)(,第一个字符就是闭括号,栈是空的。stack.pop() 返回 undefinedundefined !== '(' 为真,返回 false。答案对。这个「对」是巧合兜住的:undefined 恰好不等于任何一个开括号。哪天有人把比较改写成 if (!stack.length || stack.pop() !== pairs[char]),看着像加了层保护,其实什么都没变;再哪天有人为了「性能」先 pop 再看长度,那才真出事。

! 在 TypeScript 里干的事,是跟编译器说:这个值一定不是 null 或 undefined,你别管。它对运行时没有任何保证,编译完连痕迹都不剩。可读代码的人看到的是一句斩钉截铁的断定——栈不会空。写这句断定的人,很多时候根本没验过。

「看起来对」和「是对的」中间那口井,就是这么来的。

那篇是 AI 辅助写的。锅我不打算全甩给模型,但这个 ! 哪来的,我能猜个八九分。stack.pop()! 这个形状在训练数据里出现的次数,大概比所有算法题的正确答案加起来还多。模型见过一万遍这个句子,学到的是「这里就该这么写」的语感,不是「这里为什么安全」的推理。它复现的是一个形状,不是一个结论。

这里我犹豫了一下要不要把话说这么满——手写代码里也全是 !,我自己的老代码翻出来八成也能抓出几个。所以准确的版本是:这不是 AI 独有的毛病,是 AI 特别容易放大的一种毛病。它写得快、写得多,坏习惯在它这儿以样本量取胜。这周期的实习生,写 ! 的手感比写边界判断熟练多了。怪它没意义,它没见过我们这套代码的历史;活是它干的,锅还得我背。

扯远了,回正题。

我一开始以为,这种 bug 正是可视化工具该抓的。你一步步走 )(,走到第一个闭括号,栈空,pop 出 undefined,比较,false,返回——白纸黑字,「栈不会空」这个假设当场破功。

后来发现我想错了。

文章里确实有 ([)] 的失败演示,作者也在栈顶和期望值对不上那一刻停下来了。但 ) 开头这种输入,从头到尾没在可视化里出现过。可视化展示的是代码走完的那条路径,它能让你看见状态怎么变,看不见的是「有一条路径根本没被展示」。穷举输入不是工具的事。

抓到这条路径的,是评论区一条人写的回复。

所以我现在对这类工具的定位更清楚一点:它解决的是「这一行对哪个变量做了什么」,不是「这个函数在所有输入下对不对」。前者的痛点是真实的——反转链表最后那几行,prevcurrentnext 到底谁指谁,光瞪最终代码确实容易瞎。

let prev = null;
let current = head;

while (current !== null) {
  const next = current.next; // 先存,断链之后就找不回来了
  current.next = prev;
  prev = current;
  current = next;
}
return prev;

文章用 1→2→3→null 一步步走,箭头怎么翻、指针怎么挪,画出来比读十遍代码管用。后者的痛点,工具接不住。类型谎言和边界遗漏,得靠别的东西接。

我的土办法是 grep,搜 !as。凡是 AI 交给我的代码,出现非空断言或者类型断言,我当成挂了个待办,一条条看过去:这个值在这里真的不可能为空吗?是我读得出来的保证,还是我猜的?

有些确实能证。前两行刚做过长度检查,或者这个变量初始化时就被赋了非空值——那种断言我留着,顺手补一行注释写清楚它凭什么安全。不是给机器看的,是给三个月后的自己看的。

剩下的,一律加显式判断:

const top = stack.pop();
if (top === undefined || top !== pairs[char]) return false;

代价是多两行。换来的是这条路径上该 return false 还是该抛错,由我决定,而不是由 undefined 和某个字符恰好不相等来决定。

评论区还有人提了个改进,我挺喜欢:失败那一刻,把 target 和 pairs[char] 同时显示出来。判断就发生在比较那一行,只给读者看一个栈顶值,他得自己在脑子里跑一遍才知道为什么炸。两边都摊开,那行代码就自己说话了。

作者对这两条回复的处理,多说一句。Nazar 指出断言掩盖了空栈路径,作者没辩解,直接承认那个断言只影响静态检查、不提供运行时保证,说会更新示例,还开了个 issue 跟。被指出来还接得住的人不多。画外音:比那些一被指出问题就开始解释「这是设计意图」的强多了。

DSA View View 顺手说两句。浏览器里直接贴 TypeScript 函数,跑真代码,支持数组、矩阵、树、链表、栈、指针这些视图,内置 39 个示例,能一步步前进后退,免费,源码在 GitHub 上。这类工具我一般持保留态度——大部分可视化做得挺好看,你真正卡住的地方它偏偏不画。这个算少数我会推荐去试的,至少它把「每一行赋值之后的状态」当成了主角,不是画个漂亮动画收工。

最后落地成一条规矩。以后看任何 AI 生成的代码,我第一遍不读逻辑,先搜断言。!asany,出现一个就停一下,问自己那句「这不可能为空」我能不能当面证出来。证不出来的加检查,证出来的写注释。

一个感叹号省下四个字符,换回来一次空栈路径的惊魂。这买卖怎么算都不划算 😅

阿舟
阿舟

写代码写到一半开始怀疑人生,靠 AI 工具续命,顺手把踩过的坑都记下来。

查看主页 →