如何递归构建带优先级的逻辑查询树？

需要从一组表示逻辑/比较操作的字符串数组（例如['Name', '=', 'John', 'and', 'LastName', '!=', 'Doe']）递归构建树状数据结构。叶子节点为ComparisonNode，复合节点为LogicalNode，需支持任意数量叶子节点、运算符优先级及括号嵌套（如Price > 10 or (Category = 'Electronics' and Quantity < 100)这类复杂场景）。

已定义的TypeScript类型与接口如下：

// Define the types of operators
type LogicalOperator = 'and' | 'or' | 'not';
type ComparisonOperator = 'eq' | 'ne' | 'gt' | 'ge' | 'lt' | 'le' | 'like' | 'ilike' | 'any';
// Interface for internal nodes (logical operators)
interface LogicalNode { 
  operator: LogicalOperator;
  children: FilterNode[]; // Can be any number of children nodes
  // The above would mean 0 as left, 1 as further right etc
}
// Interface for leaf nodes (comparison)
interface ComparisonNode {
  value: string | number; // Value of the leaf node
  field: string; // Field name for comparison nodes
  operator: ComparisonOperator; // Operator for comparison nodes
}
// Union type representing all possible node types
type FilterNode = LogicalNode | ComparisonNode;

当前仅能处理简单复合查询，无法应对括号嵌套或and/or混合的复杂场景，以下是适配需求的算法与实现思路：

适合的算法与实现思路 #

1. 递归下降解析器（Recursive Descent Parser） #

这是适配递归树结构构建的最直接方案，天然支持运算符优先级与括号嵌套，逻辑清晰易实现。

核心是将表达式拆解为不同优先级的语法规则，每个规则对应一个递归函数：

• 顶层函数（处理or表达式）：循环调用and表达式解析函数，遇到or运算符时，将多个and表达式结果合并为一个LogicalNode（operator为or）
• 中间层函数（处理and表达式）：循环调用基础表达式解析函数，遇到and运算符时，合并多个基础表达式为LogicalNode（operator为and）
• 底层函数（处理基础表达式）：若当前token是(，则递归调用顶层函数解析括号内的子表达式；否则解析为ComparisonNode
• 辅助函数：负责将输入的运算符字符串（如=、!=）映射为定义好的ComparisonOperator类型，以及生成ComparisonNode实例

2. 调度场算法（Shunting-yard Algorithm） #

若偏好非递归实现，该算法可将中缀表达式转换为后缀表达式（逆波兰表示法），再通过遍历后缀表达式构建语法树，同样能完美处理优先级与括号。

核心步骤：

1. 遍历输入token数组，维护一个运算符栈与输出队列
2. 遇到字段、比较运算符、值这类token，直接加入输出队列
3. 遇到逻辑运算符时，根据优先级弹出栈中优先级更高/相等的运算符到输出队列，再将当前运算符压入栈
4. 遇到(直接压栈；遇到)则弹出栈中运算符到输出队列，直到遇到(（弹出(但不加入队列）
5. 遍历结束后，将栈中剩余运算符全部弹出到输出队列
6. 遍历后缀表达式：遇到比较表达式则生成ComparisonNode压入栈；遇到逻辑运算符则弹出对应数量的子节点，生成LogicalNode后压回栈，最终栈顶即为根节点

关键实现注意事项 #

• 运算符映射：需将输入的=、!=等字符串映射为eq、ne等定义好的ComparisonOperator类型
• 优先级规则：明确not > and > or的优先级（可根据需求调整）
• 多子节点支持：对于a and b and c这类连续同优先级的表达式，可直接生成一个包含三个子节点的and类型LogicalNode，而非嵌套结构
• TypeScript类型安全：处理token时需做好类型校验，确保生成的节点符合FilterNode联合类型要求

内容的提问来源于stack exchange，提问作者Shaun Yates