[HackerRank] Attribute Parser

https://www.hackerrank.com/challenges/attribute-parser/problem

Attribute Parser | HackerRank

문제 풀이)

1. 새로운 태그 생성

 

    - tag 이름 찾기

    - 속성 이름 찾기

    - 속성에 해당하는 값 찾기

 

    < tag > 

 

    tag이름의 경우 <tag1 name = "Name1"> 의 형태처럼 빈칸이 나올때까지 찾아도 되겠지만,

   

    속성 값이 없는 경우, 즉 <tag1>와 같은 값으로 들어올 때는 빈칸이 아닌 '>'까지 조사해주어야 한다.

 

    따라서 인덱스 1부터 문자가 ' ', '>'가 아닐 때까지가 tag임을 알 수 있다.

 

    < 속성, 값 >

 

    속성과 속성에 해당하는 값의 경우, 이 둘은 한 세트로 나온다. 문제에서 HRML은 논리적으로 맞는 문장만

 

    나옴을 보장했으니, 한 세트로 나오지 않는 경우는 생각하지 안해도 되는 것 같다.

 

    처음에는 속성, 속성이 나온 후라면 값을 찾아주는 형태로 하면 된다. 쉽게 말해 flag값을 두어 0일 경우엔

 

    속성이라고 간주하고 문자열을 찾고, 1일 경우엔 값이라고 간주하고 문자열을 찾으면 된다.

 

    각 속성과 값은 여러 개가 나올 수 있으므로, tag라는 class를 만들어 vector에 push해주는 형태로 만들었다.

 

    주의해야할 것은 <tag1 name = "Name1" value = "Value1"> 과 같은 문장이 있을 때, 속성을 찾은 뒤

 

    값을 찾을 때이다. 현재 인덱스로부터 가장 가까운 " 를 찾아, 그 이후로부터 다시 "가 나올 때까지를

 

    값으로 생각하면 된다. 다시 속성이 나올 수 있으므로, 인덱스를 1이 아닌 '2'를 증가시켜주여야 함을 잊지 말자.

 

    ( " 이후에 빈칸이 나오고 나서 문자가 나오기 때문 )

 

    < tag 추가하기 >

 

    위와 같이 태그, 속성, 값을 찾아 새로 만든 tag 클래스에 추가해주었다면, 이제 이 태그를 어디에 추가할 지를

 

    고려해야 한다. 이는 stack을 이용하여 구현했다. <tag ~ > 와 같이 tag가 추가되는 형태라면 stack에 push를

 

    해주고, </tag> 와 같이 닫히는 형태라면 stack에 pop을 해주었다.

 

    태그가 추가될 때 stack이 empty 상태가 아니라면 새로 추가되는 태그의 경우 최상위 태그가 아니라는 것이고,

 

    따라서 stack.top()에 있는 태그 클래스에 선언해둔 vector<tag*> 에 새로운 태그를 push해주었다.

 

2. query 문 처리하기

 

    - . 혹은 ~ 가 아니라면 태그 이름이다.

 

    말 그대로 .이나 ~가 아닌 경우 태그 이름으로 간주하고 string 변수에 넣어주자.

 

    이후에 .이나 '~'의 경우 string 변수에 넣어둔 태그 이름을 이용하여 tag를 찾아준다.

 

    만약 tag이름을 찾지 못했다면 Not Found! 를 출력해준다.

 

    '.'이었을 경우 반복하고, '~'의 경우 이제 속성이름이 나온다는 것이므로 속성이름을 빼내어

 

    태그 이름을 통해 찾은 tag의 속성 목록에 존재하는 지 찾아보고 존재한다면 값을 출력,

 

    존재하지 않는다면 Not Found!를 출력해주면 된다.

 

3. 주의    

 

    - 태그 이름은 'tag' + @ 가 아니라, 'a' 와 같이 tag가 붙지 않아도 된다.

 

    - 속성과 값은 여러 개일수도, 없을 수도 있다.

    

    - tag가 존재하지 않거나, 속성이 존재하지 않는 등의 예외처리

 

< 소스 코드 >

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;

class tag
{
public:
	tag(){}
	tag(const string& tagname) : m_tagname(tagname) {}
	~tag(){}

public:
	vector<string> m_attribute;
	vector<string> m_value;
	vector<tag*> m_next;
	string m_tagname;
};

int main() 
{
	vector<tag*> heads;
	stack<tag*> tagStack;
	int n, q;
	cin >> n >> q;
	while (cin.get() != '\n');

	for (int i = 0; i < n; ++i)
	{
		string strInput = "";		
		getline(cin, strInput);

		if (strInput[1] == '/')
		{
			tagStack.pop();
			continue;
		}
		
		string tagname = "";
		// tag name
		int j;
		for (j = 1; strInput[j] != ' ' && strInput[j] != '>'; ++j)
			tagname += strInput[j];
		j++;
		// new tag
		tag* newTag = new tag(tagname);
		
		int flag = 0; // 0 : attribute / 1 : value
		while (j < strInput.size())
		{
			string tmp = "";
			// attribute
			if (!flag)
			{
				for (; strInput[j] != ' '; j++)
					tmp += strInput[j];
				newTag->m_attribute.push_back(tmp);
			}
				
			// value
			else
			{
				j = strInput.find('\"', j) + 1;
				for (; strInput[j] != '\"'; j++)
					tmp += strInput[j];
				newTag->m_value.push_back(tmp);
				j += 2;
			}
			flag = !flag;
		}

		// push
		if (tagStack.empty())
			heads.push_back(newTag);
		else
			tagStack.top()->m_next.push_back(newTag);
		tagStack.push(newTag);
	}

	for (int i = 0; i < q; ++i)
	{
		string strInput = "";
		getline(cin, strInput);
		tag* curTag = NULL;
		string tagName = "";

		int j = 0;
		while (j < strInput.size())
		{
			if (strInput[j] == '.' || strInput[j] == '~')
			{
				bool bFlag = false;
				// 최상위 태그 (heads)
				if (curTag == NULL)
				{
					for (int t = 0; t < heads.size(); ++t)
					{
						if (heads[t]->m_tagname == tagName)
						{
							curTag = heads[t];
							bFlag = true;
							break;
						}
					}
				}
				// 현재 가리키고 있는 태그에서 확인
				else
				{
					for (int t = 0; t < curTag->m_next.size(); ++t)
					{
						if (curTag->m_next[t]->m_tagname == tagName)
						{
							curTag = curTag->m_next[t];
							bFlag = true;
							break;
						}
					}
				}
				// 태그를 발견하지 못한 경우
				if (!bFlag)
				{
					cout << "Not Found!\n";
					break;
				}

				// 태그 name 초기화
				tagName = "";

				// ~가 나온 경우
				if (strInput[j] == '~')
				{
					j++;
					// 속성 이름 받아오기
					string st = strInput.substr(j, strInput.size() - j);
					string result = "";
					// 속성 이름이 존재할 경우 속성에 해당하는 값 받아오기
					for (int t = 0; t < curTag->m_attribute.size(); ++t)
					{
						if (st == curTag->m_attribute[t])
						{
							result = curTag->m_value[t];
							break;
						}
					}
					if (result == "")
						cout << "Not Found!\n";
					else
						cout << result << '\n';

					break;
				}
			}
			// 태그 이름 저장
			else
				tagName += strInput[j];
			j++;
		}
	}

	return 0;
}