항 생성기 | cho.sh

문제

수식(formula)은 그림 1(a)의 문법에 따라 정의된다. 어떤 수식이 그림 1(b)의 문법도 만족하면 그 수식은 정규형(Normal Form, NF)이라고 한다.

<formula>  ::= <variable> | (+<formulae>) | (*<formulae>)
<variable> ::= 영어 알파벳 소문자 하나
<formulae> ::= <formula> | <formula><formulae>

그림 1(a). 수식의 일반 문법.

<NF_formula> ::= <term> | (+<terms>)
<term>       ::= <variable> | (*<variables>)
<terms>      ::= <term><term> | <term><terms>
<variables>  ::= <variable><variable> | <variable><variables>

그림 1(b). 정규형 수식의 문법.

수식은 아래의 재작성 규칙을 이용해 정규형으로 변환한다. 여기서 F는 하나의 수식, S는 비어 있지 않은 수식들의 나열, s와 s'는 비어 있을 수도 있는 수식들의 나열이다. 규칙 q -> r를 적용한다는 것은 수식에서 패턴 q와 일치하는 부분을 r로 바꾸는 것을 뜻하며, 그림 2에 그 예가 있다. 더 이상 적용할 규칙이 없으면 변환이 끝난다. 변환은 모든 수식에 대해 반드시 종료하며, 어떤 규칙을 어느 부분에 어떤 순서로 적용하든 결과는 항상 같다.

1. (+F)        -> F
2. (*F)        -> F
3. (+s(+S)s')  -> (+sSs')
4. (*s(*S)s')  -> (*sSs')
5. (*s(+FS)s') -> (+(*sFs')(*s(+S)s'))

(+(*(+(*ab)(+a))b))      -1->
(+(*(+(*ab)a)b))         -5->
(+(+(*(*ab)b)(*(+a) b))) -1->
(+(+(*(*ab)b)(*ab)))     -4->
(+(+(*abb)(*ab)))        -1->
(+(*abb)(*ab))

그림 2. 수식을 정규형으로 변환하는 과정.

수식 F의 정규형을 NF(F)라고 하자. 수식 F와 정수 k가 주어질 때, NF(F)에 나타나는 순서대로 다음 k개의 항(term)을 출력하는 항 생성기를 작성하라. 항이 모두 소진되면 생성기는 다시 NF(F)의 첫 항부터 이어서 진행한다. 예를 들어 F = (+(*(+(*ab)(+a))b))이면 NF(F) = (+(*abb)(*ab))이다(그림 2 참고). 첫 항을 생성하면 (*abb)가 나오고, 두 항을 더 생성하면 (*ab), 그다음 (*abb)가 나온다. NF(F)에 서로 비슷한 항이 있으면, 그림 3의 마지막 예처럼, 그 항들은 서로 다른 항으로 취급한다는 점에 유의하라. 생성기는 표준 입력에서 여러 개의 데이터 집합을 읽는다.

입력

각 데이터 집합은 F k_1 ... k_n 0 형태이며(n > 0), F는 수식이고 k_1, ..., k_n은 0이 아닌 long 정수다.

입력에는 공백을 자유롭게 사용할 수 있다.

각 수식 F는 공백을 제외하고 최대 150자이며, NF(F)의 각 항은 공백을 제외하고 최대 80자다.

입력은 파일의 끝에서 종료되며, 항상 올바른 형식으로 주어진다.

출력

각 k_i(i = 1, ..., n)에 대해 생성기는 NF(F)의 다음 |k_i|개 항을 생성한다. k_i > 0이면 그 항들을 표준 출력에 출력하고, k_i < 0이면 출력하지 않고 생성만 하여 생성기의 위치만 앞으로 옮긴다.

출력되는 각 항은 줄의 맨 앞에서 시작하며, 항을 이루는 문자들 사이에는 공백이 없다.