Postgres 16

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
CREATE TABLE expression_tree (expression_id INT, node_id INT, value VARCHAR, side VARCHAR, 
                              parent_node_id INT);
INSERT INTO expression_tree 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);

CREATE TABLE



INSERT 0 5


SELECT * from expression_tree;


expression_id
node_id
value
side
parent_node_id


1
1
-
null
null

1
2
7
L
1

1
3
*
R
1

1
4
2
L
3

1
5
3
R
3



SELECT 5


SELECT etl.expression_id, etl.parent_node_id,
            etl.node_id as left_node_id,
            etr.node_id as right_node_id,
            etl.value as left_value,
            etr.value as right_value
          FROM (SELECT * FROM expression_tree WHERE side='L') etl
          JOIN (SELECT * FROM expression_tree WHERE side='R') etr
          ON etl.expression_id = etr.expression_id
          AND etl.parent_node_id = etr.parent_node_id


expression_id
parent_node_id
left_node_id
right_node_id
left_value
right_value


1
1
2
3
7
*

1
3
4
5
2
3



SELECT 2


WITH RECURSIVE expression(left_node_id, right_node_id, left_value, right_value, expr_value) AS (
    SELECT -- parent_node_id,
           node_id as left_node_id,
           node_id as right_node_id,
           value, value, CONCAT('REPLACE[', node_id, ']')
      FROM expression_tree WHERE parent_node_id IS NULL
    UNION ALL
    SELECT -- et.parent_node_id,
           et.left_node_id, et.right_node_id,
           et.left_value, et.right_value, 

  REPLACE( expr_value, CONCAT('REPLACE[', et.parent_node_id, ']'),

  CONCAT(CASE WHEN et.left_value IN ('+', '-', '*', '/')
          THEN CONCAT('REPLACE[', et.left_node_id, ']')
          ELSE et.left_value
         END, 

  CASE WHEN et.parent_node_id=e.left_node_id
               THEN e.left_value
               ELSE e.right_value
            END,

  CASE WHEN et.right_value IN ('+', '-', '*', '/')
          THEN CONCAT('REPLACE[', et.right_node_id, ']')
          ELSE et.right_value
         END)

  ) -- END REPLACE
  
  FROM (
          SELECT etl.expression_id, etl.parent_node_id,
            etl.node_id as left_node_id,
            etr.node_id as right_node_id,
            etl.value as left_value,
            etr.value as right_value
          FROM (SELECT * FROM expression_tree WHERE side='L') etl
          JOIN (SELECT * FROM expression_tree WHERE side='R') etr
          ON etl.expression_id = etr.expression_id
          AND etl.parent_node_id = etr.parent_node_id
        ) et JOIN expression e
               ON  et.parent_node_id=e.left_node_id
               OR  et.parent_node_id=e.right_node_id
) 
SELECT * FROM expression;


left_node_id
right_node_id
left_value
right_value
expr_value


1
1
-
-
REPLACE[1]

2
3
7
*
7-REPLACE[3]

4
5
2
3
7-2*3



SELECT 3