【HackerRank】Attribute Parser

HackerRankを始めましたが、英語の記事ばかりだったので書いてみました。
C++のAttribute Parserという問題です。

問題(要約)

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を読みこむ。

#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の中です)

    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でまずタグを取ります。

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

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

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のような感じで入る。

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を消去している、ということが分かります。

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

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

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

出力

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

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;
}

参考