Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <unordered_map>
- #include <string>
- #include <sstream>
- #include <iostream>
- class Tag {
- private:
- std::string tagName;
- std::unordered_map<std::string, std::string> attributesToValue;
- std::vector<Tag> nestedTags;
- void parseOpeningTag(std::string& openingTag) {
- std::stringstream ss(openingTag);
- // lose first '<'
- char ch;
- ss >> ch;
- // get tag name
- ss >> tagName;
- // loop through attributes
- while (!ss.eof()) {
- // get attribute name
- std::string attrName;
- ss >> attrName;
- // lose '='
- ss >> ch;
- // get attribute value
- std::string attrVal;
- ss >> attrVal;
- // substring the value such that it doesn't
- // include the opening and closing quotes
- int firstQuote = attrVal.find('"');
- attrVal = attrVal.substr(firstQuote+1, attrVal.find('"', firstQuote + 1) - firstQuote - 1);
- attributesToValue[attrName] = attrVal;
- }
- }
- void processNestedTags() {
- std::string nextLine;
- while (true) {
- // get the next line and check if it's a closing tag
- // or an opening tag
- std::getline(std::cin, nextLine);
- if (nextLine[1] == '/') {
- // closing tag
- // don't recurse and break the loop
- break;
- }
- else {
- // opening tag, recurse by generating
- // a new tag and appending it's result to
- // the list of nested tags
- Tag newTag(nextLine);
- nestedTags.push_back(newTag);
- }
- }
- }
- public:
- static std::unordered_map<std::string, Tag*> allTags;
- Tag(std::string& openingTag) {
- nestedTags = std::vector<Tag>();
- parseOpeningTag(openingTag);
- processNestedTags();
- }
- inline std::string getTagName() {
- return tagName;
- }
- std::string getAttributeValue(std::string& whichAttr) {
- if (attributesToValue.find(whichAttr) != attributesToValue.end()) {
- return attributesToValue[whichAttr];
- }
- return "Not Found!";
- }
- bool getMatchingNestedTag(std::string& tagName, Tag* whichTag) {
- for (auto& x : nestedTags) {
- if (x.getTagName() == tagName) {
- whichTag = &x;
- return true;
- }
- }
- return false;
- }
- };
- // definition for static all tags
- std::unordered_map<std::string, Tag*> Tag::allTags = std::unordered_map<std::string, Tag*>();
- void getTagSequence(std::string& query, std::vector<std::string>& tagSequence, std::string& attrName) {
- // split the query into a sequence of tag names
- // and an attribute to lookup
- tagSequence.clear();
- int initialPos = 0;
- int n = 0;
- while (n != -1) {
- n = query.find('.', initialPos);
- if (n != -1) {
- // get the tag name
- std::string tagName;
- tagName = query.substr(initialPos, n - initialPos);
- tagSequence.push_back(tagName);
- // setup for the next tag in the sequence
- initialPos = n + 1;
- }
- else {
- // look for the tilde
- n = query.find('~', initialPos);
- if (n != -1) {
- // get the tag name
- std::string tagName;
- tagName = query.substr(initialPos, n - initialPos);
- tagSequence.push_back(tagName);
- attrName = query.substr(n + 1);
- n = -1;
- }
- }
- }
- }
- void processTagQuery(std::string& query) {
- auto tagSequence = std::vector<std::string>();
- std::string attrName;
- getTagSequence(query, tagSequence, attrName);
- Tag* head = nullptr;
- // begin the query with the correct head node
- if (tagSequence.size() > 0
- && Tag::allTags.find(tagSequence[0]) != Tag::allTags.end()) {
- head = Tag::allTags[tagSequence[0]];
- }
- else {
- std::cout << "Not Found!" << std::endl;
- return;
- }
- // walk through the tag sequence
- for (int i = 0; i < tagSequence.size() - 1; ++i) {
- bool check = false;
- Tag* matchingChild = nullptr;
- if (head->getTagName() == tagSequence[i]) {
- if(head->getMatchingNestedTag(tagSequence[i+1], matchingChild)){
- check = true;
- }
- }
- // couldn't find the next tag, fail
- if (!check) {
- std::cout << "Not Found!" << std::endl;
- return;
- }
- else {
- // reset the head for the next part of the loop
- head = matchingChild;
- }
- }
- // if we make it through the sequence
- // then we want to check for the value of the attribute
- // and print it
- std::cout << head->getAttributeValue(attrName) << std::endl;
- }
- int main() {
- int n, q;
- std::string firstLine;
- std::getline(std::cin, firstLine);
- std::stringstream ss(firstLine);
- ss >> n >> q;
- std::string nextLine;
- std::getline(std::cin, nextLine);
- Tag t = Tag(nextLine);
- for (int i = 0; i < q; ++i) {
- std::string nextQuery;
- std::getline(std::cin, nextQuery);
- processTagQuery(nextQuery);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement