【HackerRank】Attribute Parser

HackerRankを始めましたが、英語の記事ばかりだったので書いてみました。
C++の[Attribute Parser](https://www.hackerrank.com/challenges/attribute-parser/problem)という問題です。
## 問題(要約)
HRMLタグというものがあり、開始タグと閉じタグのペアになっている。
開始タグは、
`<タグ名 属性名 = 値 属性名2 = "値"...>`
閉じタグは、
`<\タグ名>`
となっている。

これを表す時、ネストしたタグは'.'、属性名は'~'で繋がれる。

### input
最初の行には、N Q(Nはタグの数、Qはクエリの数)
そのあとN行のタグと、Q行のクエリが続く。

- 1 ≦ N ≦ 20
- 1 ≦ Q ≦ 20
- それぞれ200行以内
- 正しいHRMLの文法で書かれている
- 属性を持たないこともある。

### output
クエリが指定するタグの値を出力する。
定義されていない場合は"Not Found!"を出力。

### sample
#### input
```
4 3
<tag1 value = "HelloWorld">
<tag2 name = "Name1">
</tag2>
</tag1>
tag1.tag2~name
tag1~name
tag1~value
```
#### output
```
Name1
Not Found!
HelloWorld
```



## 解答
### 読み込み
まず、hrmlタグとqueryを読みこむ。

```C++
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<string> hrml;
    vector<string> query;
    cin.ignore();
    string temp;
    for (int i = 0; i < N; i++)
    {
        getline(cin, temp);
        hrml.push_back(temp);
    }

    for (int i = 0; i < Q; i++)
    {
        getline(cin, temp);
        query.push_back(temp);
    }
}
```


### hrmlを一行ずつみる
次は、読み込んだtagを1行ずつ見ていきます。
(ここからmainの中です)

```C++
    map<string, string> m;
    vector<string> tags;
    for (int i = 0; i < N; i++)
    {
        temp = hrml[i];

        temp.erase(remove(temp.begin(), temp.end(), '\"'), temp.end());
        temp.erase(remove(temp.begin(), temp.end(), '>'), temp.end());

        if (temp.substr(0, 2) == "</")
        {
            tags.pop_back();
        }
        else
        {
            stringstream ss;
            ss.str("");
            ss << temp;

            string tag, name, value;
            char ch;
            ss >> ch >> tag >> name >> ch >> value;
            string temp1 = "";
            if (tags.size() > 0)
            {
                temp1 = *tags.rbegin();
                temp1 = temp1 + "." + tag;
            }
            else
            {
                temp1 = tag;
            }
            tags.push_back(temp1);
            m[*tags.rbegin() + "~" + name] = value;
            while (ss)
            {
                ss >> name >> ch >> value;
                m[*tags.rbegin() + "~" + name] = value;
            }
        }
        
    }
```
[Erase-remove](https://qiita.com/bluesky0906/items/5663bf10e5ce4628c4d1)でまずタグを取ります。

```C++
temp.erase(remove(temp.begin(), temp.end(), '\"'), temp.end());
temp.erase(remove(temp.begin(), temp.end(), '>'), temp.end());
// <tag1 value = HelloWorld こんな感じになる
```


ifは一旦放っておいて、elseの中を見ていきます。
stringstreamを使って、区切っていきます。

```C++
stringstream ss;
ss.str("");
ss << temp; // tempの中をstringstreamに

string tag, name, value;
char ch;
ss >> ch >> tag >> name >> ch >> value;
// ch = '<', tag = "tag1", name = "value", ch = '<', value = "HelloWorld"
```

tagsに既に他のデータが入ってたら、ネストしたtag名~属性名、入ってなかったらtag名~属性名をkeyとして、
値にはvalueを入れてあげる。

例えば、最初の入力ならtagには何も入っていないのでmapには
`tag1~value, HelloWorld`のような感じで入る。
2番目の入力ではtag1がtagsの中に入ってるので、mapには
`tag1.tag2~name, Name1`のような感じで入る。

```C++
string temp1 = "";
if (tags.size() > 0)
{
   temp1 = *tags.rbegin();
   temp1 = temp1 + "." + tag;
}
else
{
   temp1 = tag;
}
tags.push_back(temp1);
m[*tags.rbegin() + "~" + name] = value;

```

ここで、先ほど放っておいたif文に戻ると、閉じタグが来たら、tagsから保存しておいたtagを消去している、ということが分かります。

```C++
if (temp.substr(0, 2) == "</")
{
    tags.pop_back();
}
```

さらにタグの中に複数の属性があったらなくなるまでmに入れてあげる。

```C++
while (ss)
{
   ss >> name >> ch >> value;
   m[*tags.rbegin() + "~" + name] = value;
}
```

### 出力
最後にqueryの内容を読み込んで出力してあげれば終わり。

```C++
for (int i = 0; i < Q; i++)
{
   if (m.find(query.at(i)) == m.end())
       cout << "Not Found!" << endl;
   else
       cout << m.at(query.at(i)) << endl;
}
```

## 参考
https://www.programmingwithbasics.com/2016/09/hacker-rank-solution-program-in-c-for_85.html