Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2017
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.68 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <unordered_map>
  7. #include <string>
  8. #include <sstream>
  9. #include <iostream>
  10.  
  11. class Tag {
  12.  
  13. private:
  14.  
  15. std::string tagName;
  16. std::unordered_map<std::string, std::string> attributesToValue;
  17. std::vector<Tag> nestedTags;
  18.  
  19. void parseOpeningTag(std::string& openingTag) {
  20.  
  21. std::stringstream ss(openingTag);
  22.  
  23. // lose first '<'
  24. char ch;
  25. ss >> ch;
  26.  
  27. // get tag name
  28. ss >> tagName;
  29.  
  30. // loop through attributes
  31. while (!ss.eof()) {
  32.  
  33. // get attribute name
  34. std::string attrName;
  35. ss >> attrName;
  36.  
  37. // lose '='
  38. ss >> ch;
  39.  
  40. // get attribute value
  41. std::string attrVal;
  42. ss >> attrVal;
  43.  
  44. // substring the value such that it doesn't
  45. // include the opening and closing quotes
  46. int firstQuote = attrVal.find('"');
  47. attrVal = attrVal.substr(firstQuote+1, attrVal.find('"', firstQuote + 1) - firstQuote - 1);
  48.  
  49. attributesToValue[attrName] = attrVal;
  50.  
  51. }
  52.  
  53. }
  54.  
  55. void processNestedTags() {
  56.  
  57. std::string nextLine;
  58.  
  59. while (true) {
  60.  
  61. // get the next line and check if it's a closing tag
  62. // or an opening tag
  63. std::getline(std::cin, nextLine);
  64.  
  65. if (nextLine[1] == '/') {
  66.  
  67. // closing tag
  68.  
  69. // don't recurse and break the loop
  70. break;
  71.  
  72. }
  73. else {
  74.  
  75. // opening tag, recurse by generating
  76. // a new tag and appending it's result to
  77. // the list of nested tags
  78.  
  79. Tag newTag(nextLine);
  80. nestedTags.push_back(newTag);
  81. }
  82.  
  83. }
  84.  
  85. }
  86.  
  87. public:
  88.  
  89. static std::unordered_map<std::string, Tag*> allTags;
  90.  
  91. Tag(std::string& openingTag) {
  92. nestedTags = std::vector<Tag>();
  93. parseOpeningTag(openingTag);
  94. processNestedTags();
  95. }
  96.  
  97. inline std::string getTagName() {
  98. return tagName;
  99. }
  100.  
  101. std::string getAttributeValue(std::string& whichAttr) {
  102. if (attributesToValue.find(whichAttr) != attributesToValue.end()) {
  103. return attributesToValue[whichAttr];
  104. }
  105. return "Not Found!";
  106. }
  107.  
  108. bool getMatchingNestedTag(std::string& tagName, Tag* whichTag) {
  109. for (auto& x : nestedTags) {
  110. if (x.getTagName() == tagName) {
  111. whichTag = &x;
  112. return true;
  113. }
  114. }
  115. return false;
  116. }
  117.  
  118. };
  119.  
  120. // definition for static all tags
  121. std::unordered_map<std::string, Tag*> Tag::allTags = std::unordered_map<std::string, Tag*>();
  122.  
  123. void getTagSequence(std::string& query, std::vector<std::string>& tagSequence, std::string& attrName) {
  124.  
  125. // split the query into a sequence of tag names
  126. // and an attribute to lookup
  127.  
  128. tagSequence.clear();
  129. int initialPos = 0;
  130. int n = 0;
  131. while (n != -1) {
  132.  
  133. n = query.find('.', initialPos);
  134. if (n != -1) {
  135.  
  136. // get the tag name
  137. std::string tagName;
  138. tagName = query.substr(initialPos, n - initialPos);
  139.  
  140. tagSequence.push_back(tagName);
  141.  
  142. // setup for the next tag in the sequence
  143. initialPos = n + 1;
  144.  
  145. }
  146. else {
  147.  
  148. // look for the tilde
  149. n = query.find('~', initialPos);
  150. if (n != -1) {
  151.  
  152. // get the tag name
  153. std::string tagName;
  154. tagName = query.substr(initialPos, n - initialPos);
  155.  
  156. tagSequence.push_back(tagName);
  157.  
  158.  
  159. attrName = query.substr(n + 1);
  160.  
  161. n = -1;
  162.  
  163. }
  164. }
  165. }
  166.  
  167.  
  168. }
  169.  
  170. void processTagQuery(std::string& query) {
  171.  
  172. auto tagSequence = std::vector<std::string>();
  173. std::string attrName;
  174. getTagSequence(query, tagSequence, attrName);
  175.  
  176. Tag* head = nullptr;
  177.  
  178. // begin the query with the correct head node
  179. if (tagSequence.size() > 0
  180. && Tag::allTags.find(tagSequence[0]) != Tag::allTags.end()) {
  181. head = Tag::allTags[tagSequence[0]];
  182. }
  183. else {
  184. std::cout << "Not Found!" << std::endl;
  185. return;
  186. }
  187.  
  188.  
  189. // walk through the tag sequence
  190. for (int i = 0; i < tagSequence.size() - 1; ++i) {
  191. bool check = false;
  192. Tag* matchingChild = nullptr;
  193. if (head->getTagName() == tagSequence[i]) {
  194. if(head->getMatchingNestedTag(tagSequence[i+1], matchingChild)){
  195. check = true;
  196. }
  197. }
  198.  
  199. // couldn't find the next tag, fail
  200. if (!check) {
  201. std::cout << "Not Found!" << std::endl;
  202. return;
  203. }
  204. else {
  205. // reset the head for the next part of the loop
  206. head = matchingChild;
  207. }
  208. }
  209.  
  210. // if we make it through the sequence
  211. // then we want to check for the value of the attribute
  212. // and print it
  213. std::cout << head->getAttributeValue(attrName) << std::endl;
  214. }
  215.  
  216. int main() {
  217.  
  218. int n, q;
  219. std::string firstLine;
  220. std::getline(std::cin, firstLine);
  221. std::stringstream ss(firstLine);
  222. ss >> n >> q;
  223.  
  224. std::string nextLine;
  225. std::getline(std::cin, nextLine);
  226.  
  227. Tag t = Tag(nextLine);
  228.  
  229. for (int i = 0; i < q; ++i) {
  230. std::string nextQuery;
  231. std::getline(std::cin, nextQuery);
  232. processTagQuery(nextQuery);
  233. }
  234.  
  235. return 0;
  236. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement