SQL trick

A friend of mine posed a challenging problem today. I will restate the problem using an example.

 create table foo (
    val number ,
    lvl number);

insert into foo values (3,1);
insert into foo values (5,2);
insert into foo values (12,3);
insert into foo values (20,4);

We need to write a single SQL to convert data in foo in following form:

 (20 - (12 - (5 - 3)))

It seemed to me that the table acted like a stack with lvl = 4 indicating the top of the stack. The problem is to construct an infix expression with correct number of parenthesis.


Here is what I did:

WITH tmp AS 
   (SELECT REPLACE(WM_CONCAT(val),',','') str
    FROM   (SELECT CASE WHEN lvl > 1 THEN '(' || val || ' - ' ELSE TO_CHAR(val) END val
            FROM   foo
            ORDER BY lvl DESC)
   ),
   max_lvl AS
   (SELECT MAX(lvl) - 1 lvl
    FROM   foo)
SELECT RPAD(a.str,LENGTH(a.str) + b.lvl, ')')
FROM    tmp a,
             max_lvl b

WM_CONCAT is Oracle provided package and is part of Oracle work space manager. It combines all records in the foo into a single comma separated line. Before using WM_CONCAT function, every value is prefixed with parenthesis and post fixed with minus (-) sign except for the first level. Eventually commas are replaced by null string and closing right parenthesis are added at the end. I didn't have to write a single line of procedural code.