백준 4828번 XML

http://icpc.me/4828

4828번: XML

 

풀이

코드를 한 글자씩 읽으며 현재 상태를 저장하는 열거형 변수 now의 값과 현재 글자에 따라 적절히 처리해주었습니다. 상태가 TAG이면 태그를, AMPERSAND이면 & 다음을 읽고 있다는 의미이며 둘 다 해당되지 않는 상태는 NORMAL으로 나타냅니다. 문제가 있는 코드를 만나면 상태를 ERROR로 지정하고 읽기를 중단합니다. 코드를 모두 읽은 후 context 스택이 비었는지, 아직 태그나 & 뒤를 읽고 있는지 여부를 추가적으로 검사합니다. 

 

코드

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define l first
#define r second
#define cat(a, b) a##b
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll S = 100000 + 10, MOD = 1e9 + 7;
 
#define EXIT now = ERROR; break;
 
enum state {
    NORMAL,
    TAG,
    OPENING_TAG,
    SINGLE_TAG,
    CLOSING_TAG,
    AMPERSAND,
    LT,
    GT,
    AMP,
    HEX,
    ERROR,
};
 
bool is_normal(char c) {
    return 32 <= c and c <= 127;
}
 
bool is_hex(char c) {
    return ('0' <= c and c <= '9') or ('a' <= c and c <= 'f') or ('A' <= c and c <= 'F');
}
 
bool is_tagname(char c) {
    return ('0' <= c and c <= '9') or ('a' <= c and c <= 'z');
}
 
state after_amp(string& s) {
    if (s == "")
        return ERROR;
    else if (s == "amp")
        return AMP;
    else if (s == "lt")
        return LT;
    else if (s == "gt")
        return GT;
    if (s[0] == 'x') {
        for (int i = 1; i < s.size(); i++) {
            if (!is_hex(s[i]))
                return ERROR;
        }
        return s.size() % 2 ? HEX : ERROR;
    }
    return ERROR;
}
 
state is_valid_tag(string& name) {
    if (name == "")
        return ERROR;
    int s = 0, e = name.size();
    state ret;
    if (name[0] == '/') {
        ret = CLOSING_TAG;
        s++;
    }
    else if (name.back() == '/') {
        ret = SINGLE_TAG;
        e--;
    }
    else
        ret = OPENING_TAG;
    for (int i = s; i < e; i++) {
        if (!is_tagname(name[i]))
            return ERROR;
    }
    return ret;
}
 
void solve(string& code) {
    state now = NORMAL;
    string name;
    stack<string> context;
    for (int i = 0; i < code.size(); i++) {
        char c = code[i];
        if (!is_normal(c)) {
            EXIT
        }
        if (c == '&') {
            if (now == NORMAL) {
                now = AMPERSAND;
                name = "";
            }
            else {
                EXIT
            }
        }
        else if (c == '<') {
            if (now == NORMAL) {
                now = TAG;
                name = "";
            }
            else {
                EXIT
            }
        }
        else if (c == ';') {
            if (now == TAG) {
                EXIT
            }
            else if (now == AMPERSAND) {
                if (after_amp(name) == ERROR) {
                    EXIT
                }
                else
                    now = NORMAL;
            }
        }
        else if (c == '>') {
            if (now == TAG) {
                state result = is_valid_tag(name);
                if (result == ERROR) {
                    EXIT
                }
                else if (result == OPENING_TAG)
                    context.push(name);
                else if (result == CLOSING_TAG) {
                    string real_name = &name[1];
                    if (context.empty() or context.top() != real_name) {
                        EXIT
                    }
                    else
                        context.pop();
                }
                now = NORMAL;
            }
            else {
                EXIT
            }
        }
        else {
            if (now == TAG or now == AMPERSAND)
                name += c;
        }
    }
    if (!context.empty())
        now = ERROR;
    cout << (now == NORMAL ? "valid\n" : "invalid\n");
}
 
int main() {
    fast;
    string code;
    while (getline(cin, code))
        solve(code);
}

 

사족

열거형 처음 써봤는데 되게 좋아요

단일 태그, & 등을 먼저 지우거나 정규식을 이용한 풀이가 많은 것 같은데 그런 거 없이 잘 풀어서 왠지 기분이 좋습니다