[4828] XML

https://www.acmicpc.net/problem/4828

4828번: XML

우선 모든 문장마다 파싱을 하고, 주어진 조건에 맞는 부분들을 제거하면서 진행하는 방법을 선택했습니다.

 

 

- 2,3번의 < > &는 파싱 후 제거해도 됩니다. 올바른 문법이므로 상관없기 때문에 

 

- 4번의 16진수 부분은 &x 이후 부분이 올바른지를 확인해야 하는데,

    - 이후 부분이 a-f 혹은 A-F 그리고 0-9 사이의 문자열임을 확인합니다.

    - 이후 부분이 짝수 인지 확인합니다. (length % 2 == 0)

 

- 5,6번의 경우에는 실제로 context 스택을 생성하여 파싱한 순서대로 Opening tag를 집어넣습니다.

    - <tag/>와 같이 생긴 애들은 나중에 한번에 처리합니다

    - Closing tag를 찾고, context 스택에 집어넣었던 애를 pop하여 서로 비교해봅니다. (다르면 error)

    - Opening tag - Closing tag 비교가 끝나면 context 스택이 비었는지 확인하여 짝이 맞는지 확인합니다 (비어있지 않으면 error)

    - 이제 실제 문자열에서 태그를 제거합니다 (Opening tag와 Closing tag 둘 다)

    - 그리고 남은 <tag/>의 형태를 확인하고 제거합니다. 

 

- 1번은 모든 문법을 제거하고 남은 plaintext를 검증하면됩니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import java.util.concurrent.CompletableFuture
import java.util.regex.Matcher
import java.util.regex.Pattern
 
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var line:String?
    while (readLine().also { line = it } != null){
        try{
            var temp:String? = removeEscape(line)
            temp = removeHex(temp)
            temp = tagVerification(temp)
            plainTextVerification(temp)
        }catch (e: java.lang.RuntimeException){
            println("invalid")
            continue
        }
        println("valid")
    }
 
    br.close()
}
 
    fun String.change(vararg replacements: Pair<String, String>): String {
        var result = this
        replacements.forEach { (l, r) -> result = result.replace(l, r) }
        return result
    }
 
    fun removeEscape(line: String?): String? {
        if (line != null) {
            return line.change("&amp;" to "", "&gt;" to "", "&lt" to "")
        }
        return line
    }
 
    fun removeHex(line: String?): String? {
        val m: Matcher = Pattern.compile("&x[a-fA-F0-9]+;").matcher(line)
        while (m.find()) {
            val hex = m.group().replace("[&x;]".toRegex(), "")
            if (hex.length % 2 != 0) {
                throw RuntimeException();
            }
        }
        if (line != null) {
            return line.replace("&x[a-fA-F0-9]+;".toRegex(), "")
        }
        return line
    }
 
    fun tagVerification(line: String?): String? {
        var context = Stack<String>()
        var lineString = line
        val m: Matcher = Pattern.compile("</?[a-z0-9]+>").matcher(lineString)
        while (m.find()) {
            var tagString = m.group()
            if (tagString.startsWith("</")) {
                var openingTag = context.pop().replace("[<>/]".toRegex(), "")
                var closingTag = tagString.replace("[<>/]".toRegex(), "")
                if (openingTag != closingTag) {
                    throw RuntimeException()
                }
            } else {
                context.push(tagString)
            }
        }
        if (!context.isEmpty()) {
            throw RuntimeException()
        }
        if (lineString != null) {
            lineString = lineString.replace("</?[a-z0-9]+>".toRegex(), "")
            lineString = lineString.replace("<?[a-z0-9]+/>".toRegex(), "")
            return lineString
        }
        if (line != null) {
            lineString = line.replace("<[a-z0-9]+/>".toRegex(), "")
        }
        return lineString
    }
 
    fun plainTextVerification(line: String?): String? {
        if (line != null) {
            if (line.contains("<") || line.contains(">") || line.contains("&")) {
                throw RuntimeException()
            }
        }
        if (line != null) {
            for (c: Char in line) {
                if (c.code < 32 || 127 < c.code) {
                    throw RuntimeException()
                }
            }
        }
        return line
    }

- 추가 테스트 케이스

<b><<br/>/b>

<br<br/>/>

<a><<a/>/a>

 

다 invalid가 떠야합니다 ㅋㅋ 

이걸 생각 못해가지고 삽질 좀 했네요.