32180번 - 매달린 else

문제

아래의 else문은 둘 중 어느 if문에 대응하는 else문일까?

if(a) if(b) c; else d;

별도로 규칙을 추가하지 않는다면 컴퓨터는 이 else가 두 if 중 어느 쪽에 대응하는지 알 수 없다. 이 문제가 컴파일러에 관한 강의에서 들어보았을 매달린 else(dangling else) 문제이다.

이 문제를 해결하는 방법은 여러 가지가 있지만, 가장 대표적인 방법은 아래의 두 가지이다.

1. 모호한 else를 짝지을 수 있는 가장 가까운 if와 짝짓는다.
2. 문법적으로 중괄호 생략을 금지한다.

이 문제에서는 1번 규칙을 사용하는 소스 코드를 입력받아 2번 규칙을 사용하는 소스 코드로 변환해야 한다.

문제에서 사용할 소스 코드의 문법은 다음과 같다.

• 소스 코드에서 사용하는 토큰은 세미콜론(";"), 여는 중괄호("{"), 닫는 중괄호("}"), "if", "else", "end"로 총 6가지이다.
• 소스 코드는 0ドル$개 이상의 구문과 하나의 "end" 토큰으로 이루어진다.
• 각 구문은 아래의 셋 중 하나에 해당한다.
  • 하나의 세미콜론(";") 토큰
  • 하나의 if문
  • 하나의 if-else문
• if문은 "if" 토큰 하나와 본문 하나가 연이어 있는 형태를 가진다.
• if-else문은 "if" 토큰 하나, 본문 하나, "else" 토큰 하나, 본문 하나가 연이어 있는 형태를 가진다.
• 본문은 위에서 정의한 두 규칙 중 어느 것을 사용하느냐에 따라 다르게 구성될 수 있다.
  • 1번 규칙을 사용하는 경우, 본문은 구문 하나로 구성될 수 있다.
  • 1번 규칙 또는 2번 규칙을 사용하는 경우, 본문은 여는 중괄호("{") 토큰 하나, 0ドル$개 이상의 구문, 닫는 중괄호("}") 토큰이 연이어 있는 형태를 가질 수 있다.
• 모든 토큰은 공백 문자 1ドル$개를 사이에 두고 구분한다.

또한, 문법 요소 간의 동형 관계는 다음과 같이 주어진다.

• 두 소스 코드는 구문 수가 같고 각 구문끼리 순서대로 대응시켰을 때 동형일 경우 동형이다.
• 두 구문은 다음 중 하나에 해당하면 동형이다.
  • 두 구문이 모두 단일 세미콜론(";") 토큰일 경우
  • 두 구문이 모두 if문이며 서로 동형일 경우
  • 두 구문이 모두 if-else문이며 서로 동형일 경우
• 두 if문은 그 본문끼리 동형일 경우 동형이다.
• 두 if-else문은 두 본문을 순서대로 대응시켰을 때 동형일 경우 동형이다.
• 두 본문은 다음 중 하나에 해당하면 동형이다.
  • 두 본문이 모두 중괄호가 있으며, 구문 수가 같고 각 구문끼리 순서대로 대응시켰을 때 동형일 경우
  • 두 본문이 모두 중괄호의 유무와 상관 없이 단일 구문이며, 구문이 서로 동형일 경우

예를 들어, 1번 규칙을 고려하지 않는다면 소스 코드 if { if ; } else ; end와 소스 코드 if if { ; } else { ; } end는 동형이며, 그 이유를 다음과 같이 보일 수 있다.

• 두 소스 코드 모두 단일 구문(if { if ; } else ;와 if if { ; } else { ; })으로 이루어져 있으며, 두 구문 모두 if-else문에 해당한다.
  • 첫 번째 본문({ if ; }와 if { ; })이 모두 단일 구문으로 이루어져 있다.
    • 두 구문 모두 if문에 해당하며, 본문(;와 { ; })이 서로 일치하는 단일 구문으로 이루어져 있다.
  • 두 번째 본문(;와 { ; })이 서로 일치하는 단일 구문으로 이루어져 있다.

여러분에게 1번 규칙을 사용하는 소스 코드 $X$가 주어진다. 여러분은 이 소스 코드와 동형이면서 2번 규칙을 사용하는 소스 코드 $X'$를 찾아 출력해야 한다. 문제에서 주어진 소스 코드의 문법을 따를 때 그러한 소스 코드 $X'$는 유일함을 증명할 수 있다.

입력

첫 번째 줄에 문제에서 제시된 입력 문법을 만족하는 문자열이 주어진다. 토큰의 개수는 "end"를 포함해서 최대 1ドル,000円$개이며, 입력의 앞뒤에 불필요한 공백이 주어지지 않는다.

형식적인 입력 문법은 아래와 같다. 이때 <input_stmt>*는 <input_stmt>가 0ドル$개 이상 올 수 있다는 의미이다.

<input> ::= <input_stmt>* "end"
<input_block> ::= <input_stmt> | "{" <input_stmt>* "}"
<input_stmt> ::= ";" | <input_if>
<input_if> ::= "if" <input_block> | "if" <input_block> "else" <input_block>

출력

첫 번째 줄에 입력받은 프로그램을 파싱한 결과를 문제에서 제시된 출력 문법을 만족하도록 출력한다.

형식적인 출력 문법은 아래와 같다. 이는 위의 <input_block>에서 <input_stmt>만 제거한 것과 동일하다.

<output> ::= <output_stmt>* "end"
<output_block> ::= "{" <output_stmt>* "}"
<output_stmt> ::= ";" | <output_if>
<output_if> ::= "if" <output_block> | "if" <output_block> "else" <output_block>

제한

노트

사실 C에는 else if문이 따로 없다는 사실을 알고 있는가? 우리가 else if라고 알고 있는 구문은 사실 일반적인 else의 본문에서 중괄호를 생략하고 if문으로 채운 경우에 해당한다.