올바른 형식의 XML 문서

시간 제한1초메모리 제한128 MB

요약

여러 XML 문서를 파싱해 여섯 가지 well-formed 규칙을 모두 만족하는지 판정하고, 문서마다 결과를 출력한다.

난이도: 보통10점 중 6점
유형: 문자열, 스택, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

XML(eXtensible Markup Language)은 형식 규칙이 엄격하며, XML 파서는 올바른 형식(well-formed) 문서의 규칙을 어기는 모든 부분을 보고해야 합니다. 문서는 아래의 모든 제약을 만족할 때 올바른 형식입니다.

XML 문서는 문자 데이터나 다른 요소를 담는 요소(element)로 구성됩니다. 요소의 시작 태그에는 속성(attribute)을 선언할 수도 있습니다. 다음 문서를 살펴봅시다.

<?xml version="1.0"?>
<customer>
  <name>
    <first>John</first>
    <last>Doe</last>
  </name>
  <address>
    <street>
      <number>15</number>
      <direction>West</direction>
      <name>34th</name>
    </street>
    <city>New York</city>
    <state-code>NY</state-code>
    <zip-code format="PLUS4">10001-0001</zip-code>
    <country-code>USA</country-code>
  </address>
  <orders/>
</customer>

꺾쇠괄호 안의 식별자가 문서의 요소입니다. zip-code 요소에서 format은 속성입니다. orders를 제외한 모든 요소는 시작 태그와 끝 태그를 함께 가집니다. orders는 빈 요소(empty element)로, 끝의 />가 요소를 닫으므로 별도의 끝 태그가 필요 없습니다. 첫 번째 줄은 파서를 위한 처리 명령이며 요소가 아닙니다.

문서는 다음 규칙을 모두 지킬 때에만 올바른 형식입니다.

다른 어떤 요소에도 포함되지 않는 요소가 정확히 하나 존재합니다. 이 요소를 루트(root, 문서) 요소라고 합니다. 위 예시에서는 customer가 루트입니다.
요소는 올바르게 중첩되어야 합니다. 비어 있지 않은 요소의 시작 태그에는 대응하는 끝 태그가 있어야 합니다.
끝 태그의 이름은 시작 태그의 이름과 일치해야 합니다. 이름은 대소문자를 구분하므로 <address>로 연 요소는 </address>로 닫아야 합니다.
같은 시작 태그나 빈 요소 태그 안에서 하나의 속성이 두 번 이상 나타날 수 없습니다.
한 요소는 그 내부 어디에도 같은 이름의 요소를 포함할 수 없습니다. 예를 들어 address 요소 안에 또 다른 address 요소를 넣을 수 없습니다.
이름이 있는 모든 속성에는 값이 있어야 합니다.

입력

입력은 여러 개의 XML 문서로 이루어집니다. 각 문서는 처리 명령 <?xml version="1.0"?>만 담긴 줄로 시작합니다. 입력의 끝은 <?end?>만 담긴 줄로 표시되며, 이는 입력의 끝을 나타내는 표지일 뿐 실제 XML 처리 명령이 아닙니다. 모든 XML 문서와 마찬가지로 요소와 속성 사이의 공백은 무시합니다. 다음을 가정할 수 있습니다.

등장하는 유일한 처리 명령은 XML 버전 처리 명령이며, 각 문서의 맨 앞에만 나타납니다.
요소와 속성 이름은 대소문자를 구분합니다. 예를 들어 <Address>와 <address>는 서로 다릅니다.
요소와 속성 이름에는 영숫자와 대시(-)만 사용됩니다.
입력에 XML 주석은 없습니다.
속성 값은 항상 큰따옴표로 감쌉니다.

출력

각 XML 문서마다 한 줄씩 출력합니다. 문서가 올바른 형식이면 well-formed를, 그렇지 않으면 non well-formed를 출력합니다. 문서가 나온 순서대로 판정을 출력합니다.

예제8

예제 1

입력

<?xml version="1.0"?>
<acm-contest-problem>
        <title>A Well-Formed Problem</title>
        <text>XML, eXtensible Markup Language, is poised to become the lingua franca of
structured data communication for the foreseeable future. [...]</text>
        <input>probleme.in</input>
        <output>probleme.out</output>
</acm-contest-problem>
<?xml version="1.0"?>
<shopping-list>
        <items>
                <item quantity="1" quantity="1">Gallon of milk</item>
                <item>Frozen pizza
        </items>
</Shopping-list>
<errand-list>
        <errand>Get some cash at the ATM
                <errand>Pick up dry cleaning</errand>
        </errand>
</errand-list>
<?end?>

예상 출력

well-formed
non well-formed

예제 2

입력

<?xml version="1.0"?>
<a></a>
<?end?>

예상 출력

well-formed

예제 3

입력

<?xml version="1.0"?>
<customer>
    <name>
        <first>John</first>
        <last>Doe</last>
    </name>
    <address>
        <street>
            <number>15</number>
            <name>34th</name>
        </street>
        <zip-code format="PLUS4">10001-0001</zip-code>
    </address>
    <orders/>
</customer>
<?end?>

예상 출력

well-formed

예제 4

입력

<?xml version="1.0"?>
<address>
    <street>15</street>
    <address>Nested</address>
</address>
<?end?>

예상 출력

non well-formed

예제 5

입력

<?xml version="1.0"?>
<Root>
    <child>text</child>
</root>
<?end?>

예상 출력

non well-formed

예제 6

입력

<?xml version="1.0"?>
<tag attr="1" attr="2">text</tag>
<?end?>

예상 출력

non well-formed

예제 7

입력

<?xml version="1.0"?>
<tag attr>text</tag>
<?end?>

예상 출력

non well-formed

예제 8

입력

<?xml version="1.0"?>
<a></a>
<b></b>
<?end?>

예상 출력

non well-formed