如何用WITH RECURSIVE CTE从SQL存储的算术解析树还原表达式

我们尝试用SQL存储算术解析树（仅支持整数的+-/*二元运算），例如表达式7-2*3对应的解析树通过以下表结构存储：

CREATE TABLE expression_tree AS (
    SELECT * FROM VALUES
    (1, 1, '-', NULL, NULL), -- "-" at top
    (1, 2, '7', 'L', 1), 
    (1, 3, '*', 'R', 1), 
    (1, 4, '2', 'L', 3), 
    (1, 5, '3', 'R', 3)
    AS tmp(expression_id, node_id, value, side, parent_node_id)
)

表数据如下：

尝试用递归CTE还原原始表达式的初始代码如下：

WITH RECURSIVE expression(node_id, node_value, expr_value) AS (
    SELECT node_id, value, value FROM expression_tree WHERE parent_node_id IS NULL
    UNION ALL
    SELECT et.node_id, et.value, 
        CASE WHEN side='L' 
          THEN CONCAT(value, expr_value) 
          ELSE CONCAT(expr_value, value) 
        END
        FROM expression_tree et JOIN expression e ON  et.parent_node_id=e.node_id
) 
SELECT * FROM expression

执行结果：

当前问题：无法同时获取节点的两个子节点值，处理右子节点时会覆盖左子节点的结果，无法正确拼接出7-2*3。

解决方案 #

核心思路是从叶子节点开始向上递归，每个运算符节点必须等到左右子节点的表达式都生成后，再将两者与运算符组合。同时可以处理运算符优先级，保证表达式的运算顺序与解析树一致：

WITH RECURSIVE expression(node_id, expr_value) AS (
    -- 基准条件：叶子节点（数值节点，无下属子节点）
    SELECT node_id, value
    FROM expression_tree et
    WHERE NOT EXISTS (
        SELECT 1 FROM expression_tree child WHERE child.parent_node_id = et.node_id
    )
    UNION ALL
    -- 递归步骤：处理运算符节点，合并左右子节点的表达式
    SELECT parent.node_id,
           CONCAT(
               -- 左子节点：如果父运算符是乘除，且左子表达式包含运算符，则加括号
               CASE WHEN parent.value IN ('*', '/') AND left_child.expr_value LIKE '%[^0-9]%' 
                    THEN CONCAT('(', left_child.expr_value, ')') 
                    ELSE left_child.expr_value 
               END,
               parent.value,
               -- 右子节点：如果父运算符是加减，且右子运算符是乘除，则加括号
               CASE WHEN parent.value IN ('+', '-') AND right_child.value IN ('*', '/') 
                    THEN CONCAT('(', right_child.expr_value, ')') 
                    ELSE right_child.expr_value 
               END
           )
    FROM expression_tree parent
    -- 关联左子节点的表达式结果
    JOIN expression left_child 
        ON left_child.node_id = (SELECT node_id FROM expression_tree WHERE parent_node_id = parent.node_id AND side = 'L')
    -- 关联右子节点的表达式结果
    JOIN expression right_child 
        ON right_child.node_id = (SELECT node_id FROM expression_tree WHERE parent_node_id = parent.node_id AND side = 'R')
    -- 仅处理运算符节点
    WHERE parent.value IN ('+', '-', '*', '/')
)
-- 取出根节点的表达式，即为最终结果
SELECT expr_value AS original_expression
FROM expression
WHERE node_id = (SELECT node_id FROM expression_tree WHERE parent_node_id IS NULL);

说明 #

1. 递归方向调整：从叶子节点（数值）开始，逐步向上合并运算符与子表达式，确保每个运算符节点能同时获取左右子节点的完整表达式。
2. 优先级处理：通过CASE判断运算符优先级，自动为需要的子表达式添加括号，保证还原的表达式运算逻辑与原解析树一致（例如7-(2*3)会被正确处理为7-2*3，而如果是(7-2)*3则会保留括号）。
3. 结果准确性：最终查询根节点（无父节点的节点）的expr_value即可得到原始表达式。

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