BOJ 6380 A Well-Formed Problem
문제 내용
여러 개의 XML 문서가 주어집니다. 각 문서는 다음의 조건을 충족합니다.
- 항상
<?xml version="1.0"?>로 시작합니다. - 위의 줄을 제외한 모든 내용은
<여는-태그>,</닫는-태그>,<여닫는-태그/>와 XML 요소가 없는 텍스트로만 이루어져 있습니다.- 여는 태그와 여닫는 태그는 속성(attribute)을 포함할 수 있습니다.
- 태그 이름과 속성 이름은 영어 대소문자, 숫자,
-로만 이루어져 있습니다. 모든 이름은 대소문자를 구별합니다. - 속성의 값은
""로 감싸져 있습니다.
전체 입력은 <?end?>로 종료됩니다.
이때, 각 문서에 대해 다음의 조건을 모두 충족하는지 확인하고, 그렇다면 well-formed, 아니라면 non well-formed를 출력하세요.
- 다른 태그에 포함되지 않는 "루트 태그"가 정확히 1개입니다.
- 여는 태그는 같은 이름의 닫는 태그로 닫혀야 합니다. 이는 올바른 괄호열처럼 동작합니다.
- 하나의 여는 태그 또는 여닫는 태그에 같은 이름의 속성이 두 개 이상 있으면 안됩니다.
- 어떤 태그의 내부에 같은 이름의 태그가 있으면 안됩니다.
- 태그의 속성에는 값이 붙어 있어야 합니다.
문제 풀이
스포일러
일단<?, ?>, </, />, <, >, =, ", 그리고 <>="와 빈칸을 포함하지 않는 연속한 글자들의 묶음을 토큰으로 보고 토큰화를 진행합니다.
그 다음, 태그 단위로 묶어서 파싱을 진행할 수 있습니다. < 또는 </에서 시작하여 > 또는 />로 끝나는 묶음을 하나의 단위로 묶고, 속성이 있을 경우 속성 문법을 잘 따르는지, 중복 속성이 없는지 확인합니다.
마지막으로, 태그 구조가 올바른지 확인하면서 루트 태그의 개수와 재귀 태그 여부도 같이 확인합니다. 이는 열려 있는 태그 이름을 저장하는 스택으로 확인할 수 있습니다.