算术表达式树求值可视化

一个简单的 Python 应用程序，用于可视化算术表达式与二叉树的转换和求值过程。

项目简介

提供了一个图形化界面，帮助理解以下算法和数据结构：

• 词法分析
• 中缀表达式转后缀表达式（Shunting Yard 算法）
• 从后缀表达式构建二叉树
• 使用栈进行非递归后序遍历求值

功能演示

快速开始

环境要求

• Python 3.14 或更高版本
• uv（推荐）或 pip
• 无第三方依赖（仅使用 Python 标准库）

使用 uv（推荐）

uv run python -m pyexprtreeviz

使用 pip

python -m pyexprtreeviz

使用说明

GUI 使用流程

1. 词法分析页面: 输入中缀表达式，例如 5+3*2 或 a+b*c
2. 中缀转后缀页面: 查看中缀转后缀的算法步骤（支持自动播放）
3. 构建表达式树页面: 查看树构建过程，点击"显示 Turtle 树"查看可视化树结构
4. 表达式树求值页面: 为变量赋值（如果有），查看求值过程

支持的符号

类型	支持字符	说明
数字	0-9	单个数字
变量	a-z, A-Z	单个字母
运算符	+, -, *, /, ^	优先级: ^ > *,/ > +,-
括号	(, )	改变运算优先级

项目结构

本项目的布局结构：

eTreeViz/
├── src/
│   └── pyexprtreeviz/
│       ├── __init__.py        # 包初始化，导出核心类
│       ├── __main__.py        # 程序入口点
│       ├── core/              # 核心算法模块
│       │   ├── __init__.py
│       │   ├── expr_tree.py   # 表达式树核心实现
│       │   ├── expr_generator.py  # 随机表达式生成器
│       │   └── snapshots.py   # 算法快照收集器
│       └── gui/               # GUI 模块
│           ├── __init__.py
│           ├── app.py         # 主应用控制器
│           ├── utils.py       # UI 工具函数
│           ├── pages/         # 各个功能页面
│           │   ├── __init__.py
│           │   ├── lexical_page.py
│           │   ├── infix_to_postfix_page.py
│           │   ├── build_tree_page.py
│           │   └── evaluate_page.py
│           └── widgets/       # 自定义 UI 组件
│               ├── __init__.py
│               ├── turtle_viz.py    # Turtle 树可视化
│               └── var_popup.py     # 变量赋值弹窗
├── pyproject.toml             # 项目配置文件
├── README.md                  # 项目说明
└── LICENSE                    # Apache 2.0 许可证

技术实现细节

核心算法

1. 词法分析

• 实现位置: src/pyexprtreeviz/core/expr_tree.py 中的 ExprTree.lexical_analysis()
• 算法: 简单的字符遍历，去除空格并生成 token 列表
• 数据结构: Python 列表（list[str]）

2. 中缀转后缀

• 实现位置: src/pyexprtreeviz/core/expr_tree.py 中的 ExprTree.infix_to_postfix()
• 算法: Shunting Yard 算法（调度场算法）
• 数据结构: 栈（Python 列表模拟）和输出队列
• 时间复杂度: O(n)，n 为 token 数量
• 关键逻辑:
  • 操作数直接进入输出队列
  • 操作符根据优先级决定是否弹出栈中元素
  • 括号用于改变运算优先级

3. 构建表达式树

• 实现位置: src/pyexprtreeviz/core/expr_tree.py 中的 ExprTree.build_tree()
• 算法: 基于栈的树构建算法
• 数据结构: 栈（存储树节点）
• 时间复杂度: O(n)
• 关键逻辑:
  • 操作数创建叶子节点并入栈
  • 操作符弹出两个节点作为子节点，新节点入栈
  • 最后栈中剩余的唯一元素为树根

4. 表达式求值

• 实现位置: src/pyexprtreeviz/core/expr_tree.py 中的 ExprTree.evaluate()
• 算法: 使用栈的非递归后序遍历
• 数据结构: 栈（存储节点和访问状态）
• 时间复杂度: O(n)
• 关键逻辑:
  • 标记节点为已访问，将子节点按右左顺序入栈
  • 弹出已访问节点，计算其值（递推）
  • 叶子节点直接返回数字或变量值
  • 操作符节点递归计算左右子节点后应用运算

GUI 架构

窗口管理

• 框架: tkinter（Python 内置）
• 主窗口: ExprTreeApp 类，使用 ttk.Notebook 实现多标签页

页面设计

每个页面继承自 ttk.Frame，采用统一的布局模式：

• 步骤说明区: 显示当前步骤的描述
• 表格展示区: 使用 ttk.Treeview 显示算法过程
• 导航控制区: 上一步、下一步、自动播放、重置按钮

自动播放机制

• 使用 tkinter.after() 方法实现定时器
• 支持暂停和继续播放
• 播放间隔为 1000ms（1秒）

Turtle 可视化

• 框架: turtle（Python 内置）
• 实现位置: src/pyexprtreeviz/gui/widgets/turtle_viz.py
• 绘制方式: 使用深度优先搜索（DFS）遍历树结构
• 节点颜色: 操作符为黄色，操作数为绿色

数据结构

ExprNode

表达式树节点，使用 dataclass 定义：

@dataclass
class ExprNode:
    value: str                      # 节点值
    left: Optional[ExprNode] = None # 左子节点
    right: Optional[ExprNode] = None # 右子节点

SnapshotCollector

算法快照收集器，用于 GUI 可视化：

• InfixToPostfixSnapshot: 中缀转后缀快照
• BuildTreeSnapshot: 构建树快照
• EvaluateSnapshot: 求值快照

使用的 Python 库

本项目仅使用 Python 标准库，无第三方依赖：

• tkinter: GUI 框架
• turtle: 图形绘制
• dataclasses: 数据类定义
• typing: 类型注解
• collections.deque: 双端队列（用于 BFS 遍历）

如何修改和扩展

添加新的运算符

在 src/pyexprtreeviz/core/expr_tree.py 中的 OPERATORS 字典添加：

OPERATORS: dict[str, ExprOpr] = {
    # ... 现有运算符 ...
    "%": ExprOpr(priority=2, apply=lambda a, b: a % b),
}

支持多位数字

需要修改 lexical_analysis() 方法，实现完整的数字解析逻辑。

添加新的可视化页面

1. 在 src/pyexprtreeviz/gui/pages/ 创建新页面类，继承 ttk.Frame
2. 在 src/pyexprtreeviz/gui/app.py 的 create_widgets() 中注册新页面
3. 更新 notebook 添加标签页

修改播放速度

在各个页面的 _auto_play_next() 方法中修改 after() 的参数：

self.play_after_id = self.after(500, self._auto_play_next)  # 改为 500ms

局限性

• 仅支持单个字符的数字（0-9）和变量（a-z, A-Z）
• 不支持多位数字或多位变量名
• 仅支持二元运算符
• 没有完整的错误恢复机制
• 求值过程中如果出现除零错误，会直接抛出异常