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(3)
        , side VARCHAR(1), 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, '9',  'L', 1), 
    (2, 3, '*',  'R', 1), 
    (2, 4, '3',  'L', 3), 
    (2, 5, '+',  'R', 3),
    (2, 6, '4',  'L', 5),
    (2, 7, '5',  'R', 5),
    (3, 1, '*', NULL, null), -- "-" at top
    (3, 2, '+',  'L', 1), 
    (3, 3, '/',  'R', 1), 
    (3, 4, '13',  'L', 2), 
    (3, 5, '14',  'R', 2),
    (3, 6, '15',  'L', 3),
    (3, 7, '16',  'R', 3),
    (4, 1, '-', null, null),-- (6+(3/3)-2*3)
	(4, 2, '+', 'L', 1),
	(4, 3, '*', 'R', 1),
	(4, 4, '2', 'L', 3),
	(4, 5, '3', 'R', 3),
	(4, 6, '6', 'L', 2),
	(4, 7, '/', 'R', 2),
	(4, 8, '3', 'L', 7),
	(4, 9, '3', 'R', 7);
    
select * from expression_tree;

CREATE TABLE



INSERT 0 28




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
9
L
1

2
3
*
R
1

2
4
3
L
3

2
5
+
R
3

2
6
4
L
5

2
7
5
R
5

3
1
*
null
null

3
2
+
L
1

3
3
/
R
1

3
4
13
L
2

3
5
14
R
2

3
6
15
L
3

3
7
16
R
3

4
1
-
null
null

4
2
+
L
1

4
3
*
R
1

4
4
2
L
3

4
5
3
R
3

4
6
6
L
2

4
7
/
R
2

4
8
3
L
7

4
9
3
R
7



SELECT 28


with   recursive 
  triple as(
	select expression_id,oid
		,concat(
			case when lv in('*','+','-','/') then concat('{',lid,'}') 
            else cast(lv as varchar) end 
			,ov
			,case when rv in('*','+','-','/') then concat('{',rid,'}') 
             else cast(rv as varchar) end
			)frm
	from(
		select o.expression_id,o.node_id oId,o.value oV,o.side oSide
	  	,l.node_id lId,l.value lV
		,l.side lSide,r.node_id rId
		,r.value rV,r.side rSide
		from expression_tree O
		inner join expression_tree L on l.expression_id=o.expression_id
		      and l.parent_node_id=o.node_id and l.side='L'
		inner join expression_tree R on r.expression_id=o.expression_id 
	  		and r.parent_node_id=o.node_id and r.side='R'
	)t
)
,r as(
  	select 0 lvl, expression_id,oid,cast(frm as varchar)frm --,lid,rid
	from triple
--	where lid>0 or rid>0
	union all
	select lvl+1,r.expression_id,r.oid
		,cast(
          replace(r.frm,concat('{',t1.oid,'}'),concat('(',t1.frm,')'))
			as varchar)frm
	from r 
	inner join triple t1 on t1.expression_id=r.expression_id 
		and r.frm like concat('%{',t1.oid,'}%')
	and lvl<7
)
-- select * from triple order by expression_id,oid;

select * 
from (select *,row_number()over(partition by expression_id order by lvl desc) rn 
      from r)x
-- where rn=1
order by expression_id,lvl;


lvl
expression_id
oid
frm
rn


0
1
3
2*3
2

0
1
1
7-{3}
3

1
1
1
7-(2*3)
1

0
2
3
3*{5}
6

0
2
5
4+5
4

0
2
1
9-{3}
5

1
2
3
3*(4+5)
2

1
2
1
9-(3*{5})
3

2
2
1
9-(3*(4+5))
1

0
3
3
15/16
6

0
3
2
13+14
5

0
3
1
{2}*{3}
7

1
3
1
{2}*(15/16)
4

1
3
1
(13+14)*{3}
3

2
3
1
(13+14)*(15/16)
1

2
3
1
(13+14)*(15/16)
2

0
4
2
6+{7}
12

0
4
7
3/3
13

0
4
1
{2}-{3}
10

0
4
3
2*3
11

1
4
1
{2}-(2*3)
8

1
4
1
(6+{7})-{3}
9

1
4
2
6+(3/3)
7

2
4
1
(6+{7})-(2*3)
4

2
4
1
(6+(3/3))-{3}
6

2
4
1
(6+{7})-(2*3)
5

3
4
1
(6+(3/3))-(2*3)
1

3
4
1
(6+(3/3))-(2*3)
3

3
4
1
(6+(3/3))-(2*3)
2



SELECT 29


	select expression_id,oid
--	,oV,oSide
--  	,lId lidx,lV,lSide
--  	,rId ridx,rV,rSide
		,concat(
			case when lv in('*','+','-','/') then concat('{',lid,'}') 
            else cast(lv as varchar) end 
			,ov
			,case when rv in('*','+','-','/') then concat('{',rid,'}') 
             else cast(rv as varchar) end
			)frm
		,case when lv in('*','+','-','/') then lid else 0 end lid
		,case when rv in('*','+','-','/') then rid else 0 end rid
	from(
	select o.expression_id,o.node_id oId,o.value oV,o.side oSide
  	,l.node_id lId,l.value lV,l.side lSide
  	,r.node_id rId,r.value rV,r.side rSide
	from expression_tree O
	inner join expression_tree L on l.expression_id=o.expression_id
	      and l.parent_node_id=o.node_id and l.side='L'
	inner join expression_tree R on r.expression_id=o.expression_id 
  		and r.parent_node_id=o.node_id and r.side='R'
	)t


expression_id
oid
frm
lid
rid


1
1
7-{3}
0
3

1
3
2*3
0
0

2
1
9-{3}
0
3

2
3
3*{5}
0
5

2
5
4+5
0
0

3
1
{2}*{3}
2
3

3
2
13+14
0
0

3
3
15/16
0
0

4
1
{2}-{3}
2
3

4
2
6+{7}
0
7

4
3
2*3
0
0

4
7
3/3
0
0



SELECT 12


with --  recursive 
  cte as(
	select expression_id,oid
--	,oV,oSide
--  	,lId lidx,lV,lSide
--  	,rId ridx,rV,rSide
		,concat(
			case when lv in('*','+','-','/') then concat('{',lid,'}') 
            else cast(lv as varchar) end 
			,ov
			,case when rv in('*','+','-','/') then concat('{',rid,'}') 
             else cast(rv as varchar) end
			)frm
		,case when lv in('*','+','-','/') then lid else 0 end lid
		,case when rv in('*','+','-','/') then rid else 0 end rid
	from(
	select o.expression_id,o.node_id oId,o.value oV,o.side oSide
  	,l.node_id lId,l.value lV,l.side lSide
  	,r.node_id rId,r.value rV,r.side rSide
	from expression_tree O
	inner join expression_tree L on l.expression_id=o.expression_id
	      and l.parent_node_id=o.node_id and l.side='L'
	inner join expression_tree R on r.expression_id=o.expression_id 
  		and r.parent_node_id=o.node_id and r.side='R'
	)t
)
,r as(
  	select 0 lvl, expression_id,oid,cast(frm as varchar)frm,lid,rid
	from cte
	where lid>0 or rid>0
	union all
	select lvl+1,r.expression_id,r.oid
		,cast(
         case when t1.oid=r.lid then replace(r.frm,concat('{',t1.oid,'}'),concat('(',t1.frm,')'))
	          when t1.oid=r.rid then replace(r.frm,concat('{',t1.oid,'}'),concat('(',t1.frm,')'))
	     else r.frm
	     end  as varchar)frm
		,case when t1.oid=r.lid then t1.lid else r.lid end lid
		,case when t1.oid=r.rid then t1.rid else r.rid end rid
	from r 
	inner join cte t1 on t1.expression_id=r.expression_id 
           and ((t1.oid=r.lid) or (t1.oid=r.rid))
	and lvl<7
)
-- select * from cte order by expression_id,oid;

select * 
from (select *,row_number()over(partition by expression_id order by lvl desc) rn 
      from r)x
-- where rn=1
order by expression_id,lvl;

ERROR:  relation "r" does not exist
LINE 40:  from r 
               ^
DETAIL:  There is a WITH item named "r", but it cannot be referenced from this part of the query.
HINT:  Use WITH RECURSIVE, or re-order the WITH items to remove forward references.

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	9	L	1
2	3	*	R	1
2	4	3	L	3
2	5	+	R	3
2	6	4	L	5
2	7	5	R	5
3	1	*	null	null
3	2	+	L	1
3	3	/	R	1
3	4	13	L	2
3	5	14	R	2
3	6	15	L	3
3	7	16	R	3
4	1	-	null	null
4	2	+	L	1
4	3	*	R	1
4	4	2	L	3
4	5	3	R	3
4	6	6	L	2
4	7	/	R	2
4	8	3	L	7
4	9	3	R	7

lvl	expression_id	oid	frm	rn
0	1	3	2*3	2
0	1	1	7-{3}	3
1	1	1	7-(2*3)	1
0	2	3	3*{5}	6
0	2	5	4+5	4
0	2	1	9-{3}	5
1	2	3	3*(4+5)	2
1	2	1	9-(3*{5})	3
2	2	1	9-(3*(4+5))	1
0	3	3	15/16	6
0	3	2	13+14	5
0	3	1	{2}*{3}	7
1	3	1	{2}*(15/16)	4
1	3	1	(13+14)*{3}	3
2	3	1	(13+14)*(15/16)	1
2	3	1	(13+14)*(15/16)	2
0	4	2	6+{7}	12
0	4	7	3/3	13
0	4	1	{2}-{3}	10
0	4	3	2*3	11
1	4	1	{2}-(2*3)	8
1	4	1	(6+{7})-{3}	9
1	4	2	6+(3/3)	7
2	4	1	(6+{7})-(2*3)	4
2	4	1	(6+(3/3))-{3}	6
2	4	1	(6+{7})-(2*3)	5
3	4	1	(6+(3/3))-(2*3)	1
3	4	1	(6+(3/3))-(2*3)	3
3	4	1	(6+(3/3))-(2*3)	2