在 SQL 中存储算术解析树

Question

SQL 显然不是为此目的，但我想知道是否可以使用 SQL 作为一种挑战来做到这一点。给定一个算术解析树，例如：

7-2*3

可以表示为：

    -
   / \
  7   *
     / \
    2   3

并按如下方式存储在 SQL 中（假设

+-/*

仅对整数进行二进制运算）：

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)
)

┌───────────────┬─────────┬───────┬──────┬────────────────┐
│ expression_id ┆ node_id ┆ value ┆ side ┆ parent_node_id │
╞═══════════════╪═════════╪═══════╪══════╪════════════════╡
│             1 ┆       1 ┆ -     ┆      ┆                │
│             1 ┆       2 ┆ 7     ┆ L    ┆              1 │
│             1 ┆       3 ┆ *     ┆ R    ┆              1 │
│             1 ┆       4 ┆ 2     ┆ L    ┆              3 │
│             1 ┆       5 ┆ 3     ┆ R    ┆              3 │
└───────────────┴─────────┴───────┴──────┴────────────────┘

是否可以编写一个可以为上述内容返回

WITH RECURSIVE

的

7-2*3

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

┌─────────┬────────────┬────────────┐
│ node_id ┆ node_value ┆ expr_value │
╞═════════╪════════════╪════════════╡
│       1 ┆ -          ┆ -          │
│       2 ┆ 7          ┆ 7-         │
│       3 ┆ *          ┆ -*         │
│       4 ┆ 2          ┆ 2-*        │
│       5 ┆ 3          ┆ -*3        │
└─────────┴────────────┴────────────┘

这是它的开始：https://sqlfiddle.com/sql-server/online-compiler?id=fad7e1c0-985a-49c6-9f1b-fbbe9b83c5eb.

我在上面的困难基本上是我同时需要两个节点子节点值，否则，当它获取 R 子节点时，它将继续覆盖 L 子节点。怎么解决？

Answer 1

使用递归 CTE 进行递归聚合即使不是不可能，也是很困难的。使用临时表和循环通常更容易、更高效，直到没有可聚合的行为止。

如果您想将其保留为单个查询，那么在 SQL Server 中您可以使用递归标量函数。

该表未正确标准化，这使得情况变得更加复杂。如果不是单独的表，则值和运算符应该位于单独的列中。而且

expression_id

似乎没有必要，因为根

node_id

应该唯一标识一个表达式。

• 如果节点的值可转换为数字，则使用它。
• 否则获取子节点并将它们向上旋转到左和右......
• ...在每种情况下获取节点的递归值。
• ...并使用正确的运算符将它们组合起来。

CREATE OR ALTER FUNCTION dbo.CalculateNode (@node_id bigint)
RETURNS bigint
AS BEGIN
  RETURN (
    SELECT
      CASE
        WHEN et.value NOT LIKE '%[^0-9]%'
        THEN
          TRY_CAST(et.value AS bigint)
        ELSE
        (
          SELECT
            CASE et.value
              WHEN '+' THEN L + R
              WHEN '-' THEN ISNULL(L, 0) - R
              WHEN '*' THEN L * R
              WHEN '/' THEN L / R
              WHEN '%' THEN L % R
            END
          FROM (
              SELECT
                MIN(CASE WHEN child.side = 'L' THEN v.value END) AS L,
                MIN(CASE WHEN child.side = 'R' THEN v.value END) AS R
              FROM expression_tree child
              CROSS APPLY (SELECT dbo.CalculateNode(child.node_id)) v(value)
              WHERE child.parent_node_id = et.node_id
          ) children
        )
      END
    FROM expression_tree et
    WHERE et.node_id = @node_id
  );
END;

最后只需选择父节点

SELECT et.expression_id, dbo.CalculateNode(et.node_id) AS final_value
FROM expression_tree et
WHERE et.parent_node_id IS NULL;

db<>小提琴