백준 4828 : XML

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

4828번: XML

 

예외처리할게 매우 많은 문제다. 다행히 게시판에 Jinhan814님이 테케를 올려줘서 그 테케로 예외처리 미흡한 부분을 처리할 수 있었다.

 

문제 처리 로직은 아래와 같다.

 

1. 문자열 아스키 코드 범위 확인

2. 태그가 열리지 않은 상태에서 '>'가 들어왔는지 확인

3. '<'가 태그인지 확인 후 태그 스택에 삽입, 삭제 등 작업 수행

4. '&'가 인코딩 접두어인지 확인

 

#include <iostream>
#include <string>
#include <stack>

//#define BREAK(debug) ret=0;cout<<debug<<'\n';break
#define BREAK(debug) ret=0;break
using namespace std;

string incoding[] = { "lt;", "gt;", "amp;" };

bool validate(string s) {
	if (!s.size()) return 1;
	
	int idx = 0;
	string tag;
	string text;
	stack<string> st;
	bool ret = 1;

	while (idx < s.size()) {
		//범위 초과
		if (s[idx] < char(32)) { BREAK("oob"); }
		//부적절한 문자
		else if (s[idx] == '>') { BREAK("invalid close tag"); }
		//<가 태그인지 확인
		else if (s[idx] == '<') {
			bool closeTag = 0;
			if (idx + 1 < s.size() && s[++idx] == '/') { 
				closeTag = 1; ++idx; 
			}

			tag = "";
			while (idx < s.size() && s[idx] != '>') {
				if (!(s[idx] >= '0' && s[idx] <= '9') &&
					!(s[idx] >= 'a' && s[idx] <= 'z')) break;
				tag.push_back(s[idx]);
				++idx;
			}

			if (idx < s.size() && s[idx] == '/') {
				tag.push_back(s[idx]);
				++idx;
			}

			//닫는 괄호 없음
			if (idx >= s.size() || s[idx] != '>') { BREAK("tag not closed"); }

			if (!closeTag) {
				if (!tag.size()) { BREAK("empty tag"); }
				if (tag.back() != '/') st.push(tag);
			}
			else {
				//직전 여는 태그와 다른 태그
				if (st.empty() || st.top() != tag) { BREAK("tag not matched"); }
				st.pop();
			}
		}
		//&가 인코딩 접두어인지 확인
		else if (s[idx] == '&') {
			++idx;
			if (idx >= s.size()) { BREAK("& operator oob"); }

			if (s[idx] == 'x') {
				int hex_cnt = 0;
				++idx;
				while (idx < s.size() && s[idx] != ';') {
					if (!(s[idx] >= '0' && s[idx] <= '9') 
						&& !(s[idx] >= 'A' && s[idx] <= 'F')
							&& !(s[idx] >= 'a' && s[idx] <= 'f')) break;
					++hex_cnt;
					++idx;
				}
				if (idx >= s.size() || s[idx] != ';' || hex_cnt & 1) { BREAK("&x operator invalid"); }
			}
			else {
				//lt; or gt; or amp;인지 확인
				int j, cur_idx;
				bool checked = 0;
				for (int i = 0; i < 3; i++) {
					cur_idx = idx;
					for (j = 0; j < incoding[i].size(); j++) {
						if (s[cur_idx++] != incoding[i][j]) break;
					}
					if (j == incoding[i].size()) {
						checked = 1;
						idx = cur_idx - 1;
						break;
					}
				}
				if (!checked) { BREAK("non &x operator invalid"); }
			}
		}
		idx++;
	}

	if (!st.empty()) ret = 0;

	return ret;
}

void input() {
	string s;
	while (getline(cin, s)) {
		cout << (validate(s) ? "valid" : "invalid") << '\n';
	}
}

void solution() {
	input();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2160 kb

시간: 4 ms