2
\$\begingroup\$

I wrote a program for solving the Attribute Parser challenge on HackerRank. The challenge is to read some specified number of lines of HTML-like markup (each line no more than 200 characters; for any attributes, the = sign will be preceded and followed by a space), and perform some specified number of attribute queries (each query no more than 200 characters).

Sample Input

4 3
<tag1 value = "HelloWorld">
<tag2 name = "Name1">
</tag2>
</tag1>
tag1.tag2~name
tag1~name
tag1~value

Sample Output

Name1
Not Found!
HelloWorld

All comments and suggestions are welcome and appreciated.


#include<iostream>
#include<string>
#include<vector>
#include<climits>
#include<algorithm>
#include<map>
#include<sstream>

enum TagType { OPENING_TAG, CLOSING_TAG };

class Tag
{
private:
    std::string tag_name;
    std::map<std::string, std::string> attributes;
    TagType type;
public:
    Tag(const std::string);
    std::string search_for_attribute(const std::string);
    TagType get_type();
    std::string get_name();
};

std::vector<std::string> tokenize_string(const std::string string,
                                         const std::string delimiters)
{
    std::stringstream stream(string);
    std::string line;
    std::vector<std::string> result;
    while (std::getline(stream, line))
    {
        std::size_t previous = 0, pos;
        while ((pos = line.find_first_of(delimiters, previous)) != std::string::npos)
        {
            if (pos > previous)
                result.push_back(line.substr(previous, pos - previous));
            previous = pos + 1;
        }
        if (previous < line.length())
            result.push_back(line.substr(previous, std::string::npos));
    }
    return result;
}
/*
 * Maps the tag to its level of nesting. 0 - outermost tag, above 0 - nesting level
 * Returns a map containing the tag name as a key, and it's nesting level as a value
 */
std::map<std::string, int> map_tag_depths(std::vector<Tag>& tags)
{
    int current_level = -1;
    std::map<std::string, int> tag_depths;

    for (auto tag : tags)
    {

        if (tag.get_type() == OPENING_TAG)
        {
            current_level++;
            tag_depths.insert(std::make_pair(tag.get_name(), current_level));

        }
        else
        {
            current_level--;
        }
    }
    return tag_depths;
}

Tag::Tag(const std::string line)
{
    std::vector<std::string> tokens = tokenize_string(line,"< =\"/>");
    this->tag_name = tokens[0];
    for (auto it = tokens.begin() + 1; it != tokens.end(); it += 2)
    {
        attributes.insert(std::make_pair(*it, *(it + 1)));
    }

    type = (line[1] == '/') ? CLOSING_TAG : OPENING_TAG;
}

std::string Tag::search_for_attribute(const std::string attribute_name)
{
    auto iterator = this->attributes.find(attribute_name);
    if (iterator != attributes.end())
        return iterator->second;
    else
    {
        return "Not Found!";
    }
}
TagType Tag::get_type()
{
    return this->type;
}
std::string Tag::get_name()
{
    return tag_name;
}
void process_queries(std::vector<Tag>& tags,
                     std::vector<std::string>& queries)
{
    std::map<std::string, int> tag_depths = map_tag_depths(tags);
    for (auto query : queries)
    {
        std::vector<std::string> query_tokens = tokenize_string(query,".~");
        bool path_found = true;
        //Check if the path is valid
        for (int i = 0; i < query_tokens.size() - 1; i++)
        {
            auto it = tag_depths.find(query_tokens[i]);
            if (it == tag_depths.end() || it->second != i)
                path_found = false;
        }
        if (path_found)
        {
            //We know that the path is correct, so we can use
            //the tag name referenced last by the query
            std::string tag_name = query_tokens[query_tokens.size() - 2];

            //Name of the attribute in the query
            std::string attribute_name = query_tokens[query_tokens.size() - 1];

            //Find the tag
            for (auto it = tags.begin(); it != tags.end(); it++)
            {
                if (it->get_name() == tag_name)
                {
                    std::cout << it->search_for_attribute(attribute_name)<<'\n';
                    break;

                }
            }
        }
        else
            std::cout << "Not Found!\n";
    }
}
int main()
{
    int N, Q;
    std::cin >> N >> Q;
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

    std::vector<Tag> tags;
    while (N--)
    {
        std::string line;
        std::getline(std::cin, line);
        Tag current_tag(line);
        tags.push_back(current_tag);
    }
    std::vector<std::string> queries;
    while (Q--)
    {
        std::string query;
        std::cin >> query;
        queries.push_back(query);
    }
    process_queries(tags, queries);
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.