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),
    (2, 1, '*', NULL, NULL), -- "-" at top
    (2, 2, '-', 'L', 1), 
    (2, 3, '3', 'R', 1), 
    (2, 4, '7', 'L', 2), 
    (2, 5, '2', 'R', 2);

CREATE TABLE



INSERT 0 10


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

2
1
*
null
null

2
2
-
L
1

2
3
3
R
1

2
4
7
L
2

2
5
2
R
2



SELECT 10


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

2
1
2
3
-
3

2
2
4
5
7
2



SELECT 4


WITH RECURSIVE expression(
  expression_id, left_node_id, right_node_id,
  left_value, right_value, expr_value) AS (
    SELECT expression_id, -- 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.expression_id, -- 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
      (CASE WHEN et.parent_node_id=e.left_node_id
          THEN e.left_value
          ELSE e.right_value
       END)
  IN ('+', '-') 
  AND et.parent_node_id != 1
  THEN '(' ELSE '' END,
  
  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,

  CASE WHEN
      (CASE WHEN et.parent_node_id=e.left_node_id
          THEN e.left_value
          ELSE e.right_value
       END)
  IN ('+', '-') 
  AND et.parent_node_id != 1
  THEN ')' ELSE '' 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.expression_id = e.expression_id
               AND  (et.parent_node_id=e.left_node_id
               OR  et.parent_node_id=e.right_node_id)
) 
SELECT * FROM expression ORDER BY expression_id, left_node_id, right_node_id;


expression_id
left_node_id
right_node_id
left_value
right_value
expr_value


1
1
1
-
-
REPLACE[1]

1
2
3
7
*
7-REPLACE[3]

1
4
5
2
3
7-2*3

2
1
1
*
*
REPLACE[1]

2
2
3
-
3
REPLACE[2]*3

2
4
5
7
2
(7-2)*3



SELECT 6
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
2	1	*	null	null
2	2	-	L	1
2	3	3	R	1
2	4	7	L	2
2	5	2	R	2
expression_id	left_node_id	right_node_id	left_value	right_value	expr_value
1	1	1	-	-	REPLACE[1]
1	2	3	7	*	7-REPLACE[3]
1	4	5	2	3	7-2*3
2	1	1	*	*	REPLACE[1]
2	2	3	-	3	REPLACE[2]*3
2	4	5	7	2	(7-2)*3