在编译器前端实践中，将中缀表达式转为后缀（逆波兰）表达式的 Shunting-Yard 算法是经典范例。然而在教学与工程演示场景中，静态代码展示与公式推导往往令学习者难以把握状态转换的核心逻辑。本文聚焦于如何借助 Web 技术实现该算法的步进式可视化 —— 在动画中同步呈现词元解析、算符栈操作与输出队列构建全过程，并给出可落地的工程参数与实现要点。
1. 核心架构：三元结构 + 生成器驱动
构建一个高质量的算法可视化系统，核心在于将算法执行与渲染逻辑解耦。本方案采用三元结构：
- 词元流（Token Stream）：负责输入表达式的词法分析，将字符串拆解为操作数、算符、左 / 右括号四类词元。
- 生成器（Generator）：以 ES6 Generator 函数封装算法每一步的状态快照，包含当前输入指针位置、算符栈内容、输出队列内容与当前动作描述。生成器驱动而非直接执行，确保动画可暂停、可回退。
- 渲染引擎（Renderer）：接收状态快照，通过 DOM/CSS 或 Canvas/SVG 绘制当前算符栈与输出队列，配合颜色高亮与过渡动画呈现步骤进展。
// 生成器驱动示例
function* shuntingYardGenerator(tokens) {
const output = [], opStack = [];
for (const token of tokens) {
if (token.type === 'operand') {
output.push(token);
yield { opStack: [...opStack], output: [...output], action: `输出操作数 ${token.value}` };
}
// ... 算符与括号处理逻辑，yield 每一步状态
}
}
这种设计使控制器（Controller）可独立于算法逻辑，实现播放 / 暂停 / 单步前进 / 单步回退的交互能力，而渲染层仅需消费状态快照进行绘制。
2. 词元化：处理复杂表达式的边界条件
词法分析器（Lexer）是可视化系统的上游入口，其鲁棒性直接影响用户体验。以下是需要特殊处理的三类边界条件：
多位数与小数：连续扫描数字字符直至遇到非数字字符（含小数点），拼接为完整操作数字符串。示例输入 3.14159 + 2.718 应识别为三个词元：3.14159（操作数）、+（算符）、2.718（操作数）。
一元负号：区分减号为二元减还是一元负。简单策略为：如果当前词元为算符且前一个词元为左括号或为空，则将 - 标记为一元取反运算符 UMINUS，在后续求值阶段转换为 0 - x。复杂策略可借助正则预扫描或状态机区分。
函数名支持：对于 sin(30) + cos(45) 这类函数调用，需在词元化阶段识别函数标识符并将其作为算符压栈 —— 优先级高于所有二元算符，遵循括号闭合后自动弹出函数参数列表的语义。
典型词元化参数配置：正则模式 /^(\d+\.?\d*)|([+\-*/^()])|([a-zA-Z_]\w*)/，匹配优先级依次为数字、算符 / 括号、标识符。
3. 优先级与结合性：驱动栈操作的核心规则
Shunting-Yard 的核心决策在于算符栈的弹出时机。算法依赖两张查表实现决策：
| 算符 | 优先级 | 结合性 |
|---|---|---|
+ - |
1 | 左结合 |
* / |
2 | 左结合 |
^ |
3 | 右结合 |
左结合算符在栈顶优先级 >= 当前算符优先级时弹出；右结合算符 ^ 仅在栈顶优先级 > 当前优先级时弹出。这解释了为何 2 ^ 3 ^ 4 转为后缀是 2 3 4 ^ ^（先计算右侧 3 ^ 4，再以 2 与结果计算），而 2 - 3 - 4 转为 2 3 - 4 -（左结合，从左至右计算）。
在可视化实现中，需要在栈操作动画中明确标注每一次弹出的比较依据 ——while (opStack not empty AND precedence(top) >= precedence(current)) pop—— 并用颜色区分「比较后未弹出（等待）」与「弹出并输出」两种状态。
4. 动画同步：状态机推进的可视化参数
为使动画流畅且可控制，以下是关键工程参数：
帧率与步进粒度：推荐使用 requestAnimationFrame 驱动主循环，目标帧率 60fps。每帧推进步数通过速度滑块控制 —— 慢速模式（1 step/frame）、常速（3 steps/frame）、快速（10 steps/frame）。
过渡时长：栈内元素弹出动画建议 300ms ease-out；输出队列追加动画建议 200ms ease-in-out；当前词元高亮脉动 400ms infinite。过渡时长不宜过长，否则在快速模式下视觉上会产生延迟感。
颜色编码规范：
- 当前处理词元：
#3B82F6（蓝色），配合border: 2px solid - 算符栈顶元素（待比较）：
#F59E0B（琥珀色） - 弹出并输出动作：
#EF4444（红色）→ 变为输出队列绿色 - 输出队列已稳定元素：
#10B981（绿色） - 括号：统一使用
#8B5CF6（紫色）
回退机制：Generator 函数天然支持 yield 快照累积历史状态数组。实现时需在每次 yield 前深拷贝栈与队列状态，并在控制器层维护当前历史索引，支持向前 / 向后导航。
5. 语法树构建：从后缀到树的增量可视化
仅展示中缀→后缀的转换过程对教学而言足够，但进阶可视化可进一步将后缀表达式增量构建为二叉语法树。实现思路如下：
遍历后缀词元流，遇到操作数时创建叶节点并压入节点栈；遇到算符时弹出两个节点，将算符作为父节点、弹出的两个节点分别作为左右子节点，然后将新父节点压回栈。最终栈内唯一节点即为语法树根节点。
在动画层面，每次弹出两个节点并组合为新父节点的过程可以树形分支展开的方式呈现，配合弹性动画（spring animation）使新节点「生长」到父节点位置。这一步的可视化复杂度较高，适合作为进阶功能或交互探索入口。
6. 性能考量：长表达式的渲染优化
当输入表达式较长（如 a + b * c - d / e + f ^ g ^ h）时，输出队列与算符栈会频繁变化，DOM 操作可能成为瓶颈。优化策略包括：
- 使用 CSS
transform替代top/left定位进行位置动画，减少重排（reflow）。 - 对栈与队列容器启用
will-change: transform，提示浏览器提前创建合成层。 - 若使用 Canvas 渲染，需在每一帧开始时调用
clearRect清理画布，而非保持离屏 Canvas 增量绘制（后者在复杂场景下会引入状态残留问题）。
7. 工程部署建议
完整实现后，可考虑以下增强与部署路径：
- 导出功能：将转换后的后缀表达式或语法树导出为 LaTeX / DOT / JSON 格式，便于嵌入文档或进一步处理。
- 暗色主题：为代码编辑器风格的暗色主题提供 CSS 变量覆盖，使演示界面更契合开发者审美。
- 键盘快捷键：Space 播放 / 暂停，←/→ 单步回退 / 前进，R 重置表达式，+/- 调整速度，提升教学场景的操控效率。
参考资料
- Dijkstra, Edsger. "Shunting-yard algorithm." Wikipedia, Wikimedia Foundation. https://en.wikipedia.org/wiki/Shunting_yard_algorithm
- VisuAlgo. "Expression Tree & Shunting-yard." https://visualgo.net/en/list
内容声明：本文无广告投放、无付费植入。
如有事实性问题，欢迎发送勘误至 i@hotdrydog.com。