How to generate all strings of balanced parentheses in SQL
June 16th, 2008 By Frank Zhou
The following SQL pattern can be used to generate all strings of balanced parentheses.
variable input number
—————————-SQL Solution ————————–
SELECT str
FROM
(SELECT CASE WHEN instr(str,')(') = 0
THEN 'F'
ELSE 'T' END flag, str FROM (SELECT rpad('()', &input * 2,'()') str from dual )
)
MODEL
DIMENSION BY (0 dim)
MEASURES(str, flag)
RULES ITERATE (10000) UNTIL (instr(str[ITERATION_NUMBER+1],')(') = 0 OR flag[0] = 'F')
(
str[ITERATION_NUMBER+1] =
CASE WHEN instr(str[cv()-1],')(') >0
THEN CASE WHEN instr(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'()')>0
THEN rpad('()',least(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')')),
length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'(')))*2,'()')
||CASE WHEN length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')')) =
least(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')')),
length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'(')))
THEN rpad(')', abs(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')'))
- length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'(')) ),')')
ELSE rpad('(', abs(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')'))
- length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'('))),'(')
END||'()'||substr(str[cv()-1], instr(str[cv()-1],')(')+2 )
ELSE substr(str[cv()-1],1,instr(str[cv()-1],')(')-1)||'()'||
substr(str[cv()-1],instr(str[cv()-1],')(')+2)
END
END
);
Enter value for input: 5
old 5: ELSE 'T' END flag, str FROM (SELECT rpad('()', &input * 2,'()') str from dual )
new 5: ELSE 'T' END flag, str FROM (SELECT rpad('()', 5 * 2,'()') str from dual )
STR
----------
()()()()()
(())()()()
()(())()()
(()())()()
((()))()()
()()(())()
(())(())()
()(()())()
(()()())()
((())())()
()((()))()
STR
----------
(()(()))()
((()()))()
(((())))()
()()()(())
(())()(())
()(())(())
(()())(())
((()))(())
()()(()())
(())(()())
()(()()())
STR
----------
(()()()())
((())()())
()((())())
(()(())())
((()())())
(((()))())
()()((()))
(())((()))
()(()(()))
(()()(()))
((())(()))
STR
----------
()((()()))
(()(()()))
((()()()))
(((())()))
()(((())))
(()((())))
((()(())))
(((()())))
((((()))))
42 rows selected.
June 25th, 2010 at 6:12 am
11GR2:
variable input number
exec :input :=5;
WITH
t (str,left_cnt,right_cnt) AS (
SELECT ‘(’,1,0 FROM DUAL
UNION ALL
SELECT CAST(t.str||new_str AS VARCHAR2(20))
,left_cnt + DECODE(new_str,’(',1,0)
,right_cnt + DECODE(new_str,’)',1,0)
FROM t,(SELECT ‘(’ AS new_str FROM DUAL UNION ALL SELECT ‘)’ AS new_str FROM DUAL)
WHERE new_str = ‘(’ AND left_cnt<5
OR new_str = ‘)’ AND right_cnt<5 AND right_cnt<left_cnt
)
SELECT * FROM T WHERE left_cnt=5 AND right_cnt=5;
June 25th, 2010 at 6:13 am
forgot to put code in the pre tag:
variable input number exec :input :=5; WITH t (str,left_cnt,right_cnt) AS ( SELECT '(',1,0 FROM DUAL UNION ALL SELECT CAST(t.str||new_str AS VARCHAR2(20)) ,left_cnt + DECODE(new_str,'(',1,0) ,right_cnt + DECODE(new_str,')',1,0) FROM t,(SELECT '(' AS new_str FROM DUAL UNION ALL SELECT ')' AS new_str FROM DUAL) WHERE new_str = '(' AND left_cnt<5 OR new_str = ')' AND right_cnt<5 AND right_cnt<left_cnt ) SELECT * FROM T WHERE left_cnt=5 AND right_cnt=5;