database.sarang.net
UserID
Passwd
Database
DBMS
MySQL
PostgreSQL
Firebird
ㆍOracle
Informix
Sybase
MS-SQL
DB2
Cache
CUBRID
LDAP
ALTIBASE
Tibero
DB 문서들
스터디
Community
공지사항
자유게시판
구인|구직
DSN 갤러리
도움주신분들
Admin
운영게시판
최근게시물
Oracle Q&A 40811 게시물 읽기
No. 40811
퀴즈입니다. SQL로 구문트리화된 수식을 계산하기
작성자
김흥수(protokhs)
작성일
2015-06-01 10:29
조회수
10,772

 다음과 같은 수식이 있다고 하자

( 4 - ( 10 - 7 )) + 3) * ( 5 / 2)

이 수식을 구문트리로 다음과 같이 표현했다고 하자

with base_data as 

(

    select 1 노드번호 , '*' 연산자 , null 노드값 ,1 순서 , null 부모노드 from dual

    union select 2 노드번호 , '/' 연산자 , null 노드값 ,2 순서, 1 부모노드 from dual

    union select 3 노드번호 , '+' 연산자 , null 노드값 ,1 순서, 1 부모노드 from dual

    union select 4 노드번호 , '-' 연산자 , null 노드값 ,1 순서, 3 부모노드 from dual

    union select 5 노드번호 , null 연산자 , 3 노드값 ,2 순서, 3 부모노드 from dual

    union select 6 노드번호 , null 연산자 , 5 노드값 ,1 순서, 2 부모노드 from dual

    union select 7 노드번호 , null 연산자 , 2 노드값 ,2 순서, 2 부모노드 from dual

    union select 8 노드번호 , null 연산자 , 4 노드값 ,1 순서, 4 부모노드 from dual

    union select 9 노드번호 , '-' 연산자 , null 노드값 ,2 순서, 4 부모노드 from dual

    union select 10 노드번호 , null 연산자 , 10 노드값 ,1 순서, 9 부모노드 from dual

    union select 11 노드번호 , null 연산자 , 7 노드값 ,2 순서, 9 부모노드 from dual

)

 
 
이 데이타로 이 수식의 답을 구하는 SQL을 작성하시면 됩니다.
 
 
이 글에 대한 댓글이 총 5건 있습니다.

WITH base_data AS
(
SELECT 1 노드번호, '*' 연산자, null 노드값, 1 순서, null 부모노드 FROM dual
UNION ALL SELECT  2, '/' , null, 2, 1 FROM dual
UNION ALL SELECT  3, '+' , null, 1, 1 FROM dual
UNION ALL SELECT  4, '-' , null, 1, 3 FROM dual
UNION ALL SELECT  5, null,    3, 2, 3 FROM dual
UNION ALL SELECT  6, null,    5, 1, 2 FROM dual
UNION ALL SELECT  7, null,    2, 2, 2 FROM dual
UNION ALL SELECT  8, null,    4, 1, 4 FROM dual
UNION ALL SELECT  9, '-' , null, 2, 4 FROM dual
UNION ALL SELECT 10, null,   10, 1, 9 FROM dual
UNION ALL SELECT 11, null,    7, 2, 9 FROM dual
)
, t AS
(
SELECT ROW_NUMBER() OVER(ORDER BY MIN(rn)) rn
     , 부모노드
     , 연산자
     , MIN(노드번호1) 노드번호1
     , MIN(노드번호2) 노드번호2
     , CAST(
       '('|| 'a'||MIN(노드번호1)||'a' ||연산자|| 'a'||MIN(노드번호2)||'a' ||')'
       AS VARCHAR2(4000)) v
  FROM (SELECT 부모노드
             , ROWNUM rn
             , PRIOR 연산자 연산자
             , DECODE(순서, 1, 노드번호) 노드번호1
             , DECODE(순서, 2, 노드번호) 노드번호2
          FROM base_data
         WHERE LEVEL = 2
         START WITH 연산자 IS NOT NULL
         CONNECT BY PRIOR 노드번호 = 부모노드
         ORDER SIBLINGS BY 순서
        )
 GROUP BY 부모노드, 연산자
)
, t1 AS
(
SELECT v
  FROM (SELECT *
          FROM t
         MODEL
         DIMENSION BY (rn)
         MEASURES ( 부모노드, 연산자, 노드번호1, 노드번호2, v )
         RULES ITERATE (20)
         (
         v[0] = REPLACE( NVL(v[0], v[1])
                       , 'a'||부모노드[ITERATION_NUMBER+2]||'a'
                       ,  v[ITERATION_NUMBER+2]
                       )
         )
        )
 WHERE rn = 0
)
, t2 AS
(
SELECT v
  FROM (SELECT *
          FROM (SELECT ROWNUM rn
                     , v
                     , 노드번호
                     , 노드값
                  FROM t1 a
                     , base_data b
                 WHERE b.노드값 IS NOT NULL
                )
         MODEL
         DIMENSION BY (rn)
         MEASURES (v, 노드번호, 노드값)
         RULES ITERATE (20)
         (
           v[0] = REPLACE( NVL(v[0], v[1])
                         , 'a'||노드번호[ITERATION_NUMBER+1]||'a'
                         , 노드값[ITERATION_NUMBER+1]
                         )
         )
        )
 WHERE rn = 0
)
SELECT v
     , TO_NUMBER(
       dbms_xmlgen.getxmltype(
       'SELECT ' || v || ' FROM dual').Extract('//text()'
       ) ) x
  FROM t2
;

마농(manon94)님이 2015-06-02 11:32에 작성한 댓글입니다.
이 댓글은 2015-06-02 15:24에 마지막으로 수정되었습니다.

 역시 마농님 훌륭하십니다.

 

다음은 제가 생각한 답입니다.

결과만 보는 경우

with base_data as 
(
    select 1 노드번호 , '*' 연산자 , null 노드값 ,1 순서 , null 부모노드 from dual
    union select 2 노드번호 , '/' 연산자 , null 노드값 ,2 순서, 1 부모노드 from dual
    union select 3 노드번호 , '+' 연산자 , null 노드값 ,1 순서, 1 부모노드 from dual
    union select 4 노드번호 , '-' 연산자 , null 노드값 ,1 순서, 3 부모노드 from dual
    union select 5 노드번호 , null 연산자 , 3 노드값 ,2 순서, 3 부모노드 from dual
    union select 6 노드번호 , null 연산자 , 5 노드값 ,1 순서, 2 부모노드 from dual
    union select 7 노드번호 , null 연산자 , 2 노드값 ,2 순서, 2 부모노드 from dual
    union select 8 노드번호 , null 연산자 , 4 노드값 ,1 순서, 4 부모노드 from dual
    union select 9 노드번호 , '-' 연산자 , null 노드값 ,2 순서, 4 부모노드 from dual
    union select 10 노드번호 , null 연산자 , 10 노드값 ,1 순서, 9 부모노드 from dual
    union select 11 노드번호 , null 연산자 , 7 노드값 ,2 순서, 9 부모노드 from dual
)
, 계층화된산식 as
(
    select
        a.노드번호
        , a.연산자
        , a.노드값
        , a.순서
        , a.부모노드
        , level 레벨
        , rownum 순번
    from    base_data a 
    connect by
        prior   a.노드번호 = a.부모노드
    start with a.부모노드 is null
    order siblings by
        a.순서
)
, recur_base ( 노드번호,연산자,노드값,순서,부모노드,레벨,순번,연산결과 ) as
(
    select
        a.노드번호
        , a.연산자
        , a.노드값
        , a.순서
        , a.부모노드
        , a.레벨
        , a.순번
        , ','||a.노드값||','
    from    계층화된산식 a
    where   a.순번 = ( select count(*) from base_data )
    union all
    select
        b.노드번호
        , b.연산자
        , b.노드값
        , b.순서
        , b.부모노드
        , b.레벨
        , b.순번
        , case when b.레벨 < a.레벨 then
            ','||
            case
                when b.연산자 = '+' then
                    (to_number(substr(a.연산결과,instr(a.연산결과,',',1,1) + 1, instr(a.연산결과,',',1,2) - instr(a.연산결과,',',1,1) - 1)) + 
                    to_number(substr(a.연산결과,instr(a.연산결과,',',1,2) + 1, instr(a.연산결과,',',1,3) - instr(a.연산결과,',',1,2) - 1)))
                when b.연산자 = '-' then
                    (to_number(substr(a.연산결과,instr(a.연산결과,',',1,1) + 1, instr(a.연산결과,',',1,2) - instr(a.연산결과,',',1,1) - 1)) - 
                    to_number(substr(a.연산결과,instr(a.연산결과,',',1,2) + 1, instr(a.연산결과,',',1,3) - instr(a.연산결과,',',1,2) - 1)))
                when b.연산자 = '*' then
                    (to_number(substr(a.연산결과,instr(a.연산결과,',',1,1) + 1, instr(a.연산결과,',',1,2) - instr(a.연산결과,',',1,1) - 1)) * 
                    to_number(substr(a.연산결과,instr(a.연산결과,',',1,2) + 1, instr(a.연산결과,',',1,3) - instr(a.연산결과,',',1,2) - 1)))
                when b.연산자 = '/' then
                    (to_number(substr(a.연산결과,instr(a.연산결과,',',1,1) + 1, instr(a.연산결과,',',1,2) - instr(a.연산결과,',',1,1) - 1)) / 
                    to_number(substr(a.연산결과,instr(a.연산결과,',',1,2) + 1, instr(a.연산결과,',',1,3) - instr(a.연산결과,',',1,2) - 1)))
            end || substr(a.연산결과, nvl(nullif(instr(a.연산결과,',',1,3),0),length(a.연산결과)))
        else
            ',' || b.노드값 || a.연산결과
        end
    from    recur_base a
            , 계층화된산식 b
    where   a.순번 - 1 = b.순번
)
select
    to_number(replace(a.연산결과,',','')) 결과
from    recur_base a
where   a.순번 = 1
/
 
 
원래의 산식을 복구하고 결과도 보는 경우
with base_data as 
(
    select 1 노드번호 , '*' 연산자 , null 노드값 ,1 순서 , null 부모노드 from dual
    union select 2 노드번호 , '/' 연산자 , null 노드값 ,2 순서, 1 부모노드 from dual
    union select 3 노드번호 , '+' 연산자 , null 노드값 ,1 순서, 1 부모노드 from dual
    union select 4 노드번호 , '-' 연산자 , null 노드값 ,1 순서, 3 부모노드 from dual
    union select 5 노드번호 , null 연산자 , 3 노드값 ,2 순서, 3 부모노드 from dual
    union select 6 노드번호 , null 연산자 , 5 노드값 ,1 순서, 2 부모노드 from dual
    union select 7 노드번호 , null 연산자 , 2 노드값 ,2 순서, 2 부모노드 from dual
    union select 8 노드번호 , null 연산자 , 4 노드값 ,1 순서, 4 부모노드 from dual
    union select 9 노드번호 , '-' 연산자 , null 노드값 ,2 순서, 4 부모노드 from dual
    union select 10 노드번호 , null 연산자 , 10 노드값 ,1 순서, 9 부모노드 from dual
    union select 11 노드번호 , null 연산자 , 7 노드값 ,2 순서, 9 부모노드 from dual
)
, 계층화된산식 as
(
    select
        a.노드번호
        , a.연산자
        , a.노드값
        , a.순서
        , a.부모노드
        , level 레벨
        , rownum 순번
    from    base_data a 
    connect by
        prior   a.노드번호 = a.부모노드
    start with a.부모노드 is null
    order siblings by
        a.순서
)
, recur_base ( 노드번호,연산자,노드값,순서,부모노드,레벨,순번,연산결과,연산식결과 ) as
(
    select
        a.노드번호
        , a.연산자
        , a.노드값
        , a.순서
        , a.부모노드
        , a.레벨
        , a.순번
        , ','||a.노드값||','
        , ','||a.노드값||','
    from    계층화된산식 a
    where   a.순번 = ( select count(*) from base_data )
    union all
    select
        b.노드번호
        , b.연산자
        , b.노드값
        , b.순서
        , b.부모노드
        , b.레벨
        , b.순번
        , case when b.레벨 < a.레벨 then
            ','||
            case
                when b.연산자 = '+' then
                    (to_number(regexp_substr(a.연산결과, '[^,]+', 1, 1)) + 
                    to_number(regexp_substr(a.연산결과, '[^,]+', 1, 2)))
                when b.연산자 = '-' then
                    (to_number(regexp_substr(a.연산결과, '[^,]+', 1, 1)) - 
                    to_number(regexp_substr(a.연산결과, '[^,]+', 1, 2)))
                when b.연산자 = '*' then
                    (to_number(regexp_substr(a.연산결과, '[^,]+', 1, 1)) *
                    to_number(regexp_substr(a.연산결과, '[^,]+', 1, 2)))
                when b.연산자 = '/' then
                    (to_number(regexp_substr(a.연산결과, '[^,]+', 1, 1)) /
                    to_number(regexp_substr(a.연산결과, '[^,]+', 1, 2)))
            end || substr(a.연산결과, nvl(nullif(instr(a.연산결과,',',1,3),0),length(a.연산결과)))
        else
            ',' || b.노드값 || a.연산결과
        end
        , case when b.레벨 < a.레벨 then
            ','||
            case when regexp_count(regexp_substr(a.연산식결과, '[^,]+', 1, 1),'\+|\-|\*|/') > 0 then
                '( '||regexp_substr(a.연산식결과, '[^,]+', 1, 1) ||' )'
            else
                regexp_substr(a.연산식결과, '[^,]+', 1, 1)
            end
             || ' '||b.연산자||' '||
            case when regexp_count(regexp_substr(a.연산식결과, '[^,]+', 1, 2),'\+|\-|\*|/') > 0 then
                '( '||regexp_substr(a.연산식결과, '[^,]+', 1, 2) ||' )'
            else
                regexp_substr(a.연산식결과, '[^,]+', 1, 2)
            end
            || substr(a.연산식결과, nvl(nullif(instr(a.연산식결과,',',1,3),0),length(a.연산식결과)))
        else
            ',' || b.노드값 || a.연산식결과
        end
    from    recur_base a
            , 계층화된산식 b
    where   a.순번 - 1 = b.순번
)
select
    replace(a.연산결과,',') || ' = ' ||
    replace( a.연산식결과,',')
from    recur_base a
where   a.순번 = 1
 
 
 
김흥수(protokhs)님이 2015-06-02 17:06에 작성한 댓글입니다.

 마농님 질문이 있는데요...

 

제가 문제를 푼 방법은 구문트리가 어차피 push down automata 이니까 스택을 쓰는 것이기 때문에

아이디어가 전혀 새로울 것이 없는 것인데요...(어찌보면 좀 구질구질...)

님의 방법은 수학에서 변수로 치환하는 것을 역으로 연속적으로 적용하여 원래의 식을 구성하는 방식으로 접근하셨는데요...정말 참신해서 놀랐습니다.

이런 아이디어가 제가 퀴즈를 낸 후에 생각해내신건가요? 아니면 그전부터 이런 고민을 하신 적이 있으셨던건가요?

김흥수(protokhs)님이 2015-06-03 09:15에 작성한 댓글입니다.

글쎄요...
말씀하신 구질구질한 방식은 제겐 오히려 신선했네요. ^^
또 하나 배워갑니다.
몇몇 퀴즈는 원래 알고 있는 내용이었구요.
이번 퀴즈는 새로 고민해서 풀었네요.
물론 과거에 풀었던 문제들의 경험이 밑바탕이 되었겠지요.

마농(manon94)님이 2015-06-03 09:53에 작성한 댓글입니다.
이 댓글은 2015-06-03 09:54에 마지막으로 수정되었습니다.

 마농님 답변 감사합니다.

 

제가 지금까지 낸 퀴즈는 사실 어떤 한 문제를 풀기 위한 과정에서 생각해낸 문제들입니다.

다음 퀴즈가 그 과정의 마지막 단계이고 그 다음이 최종 보스입니다.

나머지 퀴즈들에도 관심 부탁드립니다.

^^

김흥수(protokhs)님이 2015-06-03 12:46에 작성한 댓글입니다.
[Top]
No.
제목
작성자
작성일
조회
40814PK의 성능차이 문의드립니다. [1]
궁금
2015-06-02
8718
40813UPDATE 쿼리인데 속도 문제 [2]
최인수
2015-06-02
7891
40812쿼리 질문드립니다. [2]
2015-06-02
7121
40811퀴즈입니다. SQL로 구문트리화된 수식을 계산하기 [5]
김흥수
2015-06-01
10772
40810퀴즈입니다. 부분수열의 순열들을 모두 구하기 (공집합은 제외) [3]
김흥수
2015-05-29
8979
40809퀴즈입니다. SQL로 집합의 모든 순서관계 순서쌍 구하기 [4]
김흥수
2015-05-28
9142
40808퀴즈입니다. 공집합을 제외한 모든 멱집합의 원소를 출력하는 SQL [4]
김흥수
2015-05-27
8970
Valid XHTML 1.0!
All about the DATABASE... Copyleft 1999-2024 DSN, All rights reserved.
작업시간: 0.017초, 이곳 서비스는
	PostgreSQL v16.4로 자료를 관리합니다