백준4828번 - XML 자바스크립트(Node.js)풀이

난이도: 플래티넘 4

문제
인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시한 부작용도 존재하기에, 문법이 맞게 되었는지를 판정하는 파서가 필요하게 되었다. 그러나 이다솜은 XML을 할 줄 모르기에 여러분이 판독기를 구현해야 한다.

우리가 XML 문서의 형식이 유효한지 판별하는 기준은 다음과 같다.

평문---32~127 사이에 있는(32, 127도 포함) ASCII코드값으로 이루어지며, 다음 문자는 포함되면 안 된다: <, >, &
다음과 같은 문자열:
&lt;
&gt;
&amp;
이것들은 각각 <, >, &를 인코딩한다.
&xHEX; HEX는 양의 짝수 자릿수의 16진수여야 하며, 0~9 또는 알파벳 A~F 대소문자로 이루어진다.
<tag> 여는 태그이다. 태그는 숫자 또는 알파벳 소문자로 이루어진 문자열이어야 한다. 이 태그는 context 스택에 push된다.
<tag/> 이 태그는 context 스택에 push되지 않는다.
</tag> 닫는 태그이다. context 스택의 맨 위에 있는 태그를 pop하게 된다. 단, 이때 맨 위에 있는 태그와 이 태그의 문자열이 일치해야 한다.
문서 전체가 파싱된 후에는 context 스택은 비어 있어야 한다. 또한, 빈 문자열 역시 유효하다고 판정한다.

 

입력
여러 줄의 입력이 주어진다. 각 줄에 대해 유효한 XML 문법인지를 판별한다. 각 줄은 ASCII 코드 값이 32~127인 문자로만 이루어져 있으며, 비어 있는 줄이 들어올 수도 있다. 입력은 파일 끝에서 종료된다.

 

출력
각 줄에 대하여, 해당 줄이 유효한 XML 문법을 가지고 있다면 valid를, 그렇지 않다면 invalid를 출력한다.

 

 

출처

ICPC > Regionals > North America > Rocky Mountain Regional > 2009 Rocky Mountain Regional Contest C번

 

 

테스트케이스

Home - 2009 Rocky Mountain Regional ACM Contest Information

위 사이트에서 zip file 내려받은 후 C폴더 참조

 

 

알고리즘 분류

- 자료 구조
- 문자열
- 스택
- 파싱
- 정규 표현식

 

---

스택을 이용한 파싱문제. 정규표현식을 이용하였다.

문제의 해결 과정을 크게 3단계로 나누어서 풀이하였다.

 

1. 정상적인 특수기호 제거와, 제거전 닫히는태그 검사

2. 태그검사

3. 올바르지 않은 특수기호 검사

 

이 순서대로 진행하지 않으면 아래 코드에서 제대로 XML 검사를 진행하기 힘드니

순서대로 진행해보도록 하자!

 

 

1. 정상적인 특수기호 제거와, 제거전 닫히는 태그 검사

XML에서 텍스트로 '< , > , &'와 같은 특수문자를 표현하기 위한 기호인 '&(lt|gt|amp)',

16진수의 수를 표현하기 위한 기호인 x([a-fA-F0-9]{2})를 모두 제거해주었다.

 

여기서 주의할 점은 rst플래그를 이용해 '<[^/a-z0-9]' 정규식을 검사하고 시작해주었다는 것이다.

원래는 XML문법에 틀린 표현이지만, 특수기호들을 제거해주는 방법으로 풀이를 진행하다보면 틀린 표현이 맞게 바뀌는 경우가 생길수도 있다. 아래의 테스트케이스가 그 예시이다.

 

 

위 케이스의 경우 열리는 태그와 닫히는 태그가 정상적으로 묶여있지않아 원래대로면 invalid가 출력되어야 하지만, 빈 태그인 <a/>가 제거당한 후 태그검사를 시작하면 열리는 태그와 닫히는 태그가 쌍으로 묶여있는것처럼 보여 valid가 출력되게 된다. 이러한 경우를 방지하기 위해 시작 전에 태그 안에 처음 오는 문자가 태그 조건에 만족하지 못하는 경우 invalid를 출력하도록 rst 플래그를 설정하였다.

 

 

2.태그검사

먼저 빈태그를 제거하고 스택을 이용하여 열리는 태그와 닫히는 태그가 제대로 쌍을 이루고 있는지 검사하였다.

만약 검사하고자 하는 태그가 열리는 태그라면 스택에 넣고, 닫히는 태그라면 스택을 팝하여 나온 데이터와 검사한다.

이때 쌍이 맞으면 패스하고, 쌍이 맞지 않다면 그자리에 &문자를 입력한다. &문자를 넣은 이유는 따로 플래그나 귀찮은 코드를 작성하지 않고 3단계에서 오답처리를 하기 위해서이다.

 

 

3.올바르지 않은 특수기호검사

특수기호와 태그들은 '<, >, &'를 포함한다. 위에서 정상적인 특수기호들을 전부 제거했으니, 아직까지 저런 기호가 남아있다면 그건 올바르지 않은 특수기호이다. 따라서 이러한 기호들이 있다면 rst플래그에 특수기호 검출 결과를 or하여 이 결과가 참이라면 'invalid', 거짓이라면 'valid'가 출력되게 프로그램 하였다.

 

 

 

전체 코드

const fs = require('fs');
let str = '';

(function(){
    const inputs = (
        process.platform === 'linux'
            ? fs.readFileSync('/dev/stdin').toString().trim()
            : "<a><<a/>/a>"
    ).split('\n');

    for(let i=0; i<inputs.length; i++){
        let input = inputs[i];
        let stack = [];

        // Phase 1
        let rst = /<[^/a-z0-9]/.test(input);
        input = input.replace(/&(lt|gt|amp);/g, '');
        input = input.replace(/&x([a-fA-F0-9]{2})+;/g, '');

        // Phase 2
        input = input.replace(/<[a-z0-9]+\/>/g, '');
        input = input.replace(/<\/?[a-z0-9]+>/g, function (re){
            if(re.startsWith('</')){
                if(!(stack.pop() == re.replace(/[<>/]/g, ''))){
                    return "&";
                }
            } else{
                stack.push(re.replace(/[<>/]/g, ''))
            }
            return "";
        });

        // Phase 3
        rst |= /(<|>|&)/.test(input);

        if(rst || stack.length > 0)
            console.log("invalid");
        else
            console.log("valid");
    }
})();