XML 유효성 검사

인터넷 프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 늘 학생들에게 XML의 장점을 강조한다. 하지만 잘못 사용하면 큰 문제를 일으킬 수 있는 위험한 부작용도 있어서, 문서의 문법이 올바른지 판정하는 파서가 필요하다. 이다솜은 XML을 다룰 줄 모르기에, 여러분이 대신 판독기를 구현해야 한다.

XML 문서가 유효한지는 다음 규칙으로 판별한다. 문서는 아래 요소들이 순서대로 이어진 것으로 해석하며, 어느 위치에서든 규칙에 맞지 않는 부분이 나오면 그 문서는 유효하지 않다.

1. 평문: ASCII 코드값이 32 이상 127 이하(32와 127 포함)인 문자로 이루어진다. 단, <, >, & 세 문자는 평문으로 쓸 수 없다.
2. 이스케이프 문자열: 다음 문자열은 각각 <, >, &를 인코딩한 것으로 유효하다.
   • < → <
   • > → >
   • & → &
3. 16진 이스케이프: &xHEX; 형태의 문자열. 여기서 HEX는 길이가 양의 짝수인 16진수 문자열이어야 하며, 09 또는 알파벳 AF(대문자와 소문자 모두 허용)로 이루어진다.
4. 여는 태그 <tag>: tag는 소문자 알파벳 또는 숫자로 이루어진 한 글자 이상의 문자열이어야 한다. 이 태그 이름은 컨텍스트 스택에 push된다.
5. 스스로 닫는 태그 <tag/>: 이 태그는 컨텍스트 스택에 push되지 않는다.
6. 닫는 태그 </tag>: 컨텍스트 스택의 맨 위 값을 pop한다. 단, 이때 스택의 맨 위 태그 이름이 이 태그 이름과 일치해야 한다.

문서 전체를 파싱한 뒤에는 컨텍스트 스택이 비어 있어야 한다. 빈 문자열 역시 유효한 것으로 판정한다.

여러 줄이 입력으로 주어진다. 각 줄이 유효한 XML 문법인지 판별한다. 각 줄은 ASCII 코드값이 32 이상 127 이하인 문자로만 이루어지며, 빈 줄이 들어올 수도 있다. 입력은 파일의 끝(EOF)에서 종료된다.

각 줄에 대해, 그 줄이 유효한 XML 문법이면 valid를, 그렇지 않으면 invalid를 출력한다.