Considering so many complaints about problem being marked "Medium", I would like to say, in fact, that is a clue about the solution. Scrolling through discussions, we can find several lengthy and complicated solutions. It isn't supposed to be that way.
The first most important step towards solving any problem is to read the problem well, and use all the information provided in the description properly. Failing to do that, the result will be messy code. Following line from constraints gives a big hint :All tag names are unique and the HRML source program is logically correct.
This means most of the hard-work had already been done. If we ignore this, we will be just writing needless code doing pointless computations. In stead, if we use the info properly, we'll surely get far elegant solution. Here's my approach for interested coders:#include <iostream> #include <map> using namespace std; map <string, string> tagMap; void createMap(int &n, string pretag) { if(!n) return; string line, tag, attr, value; getline(cin, line); int i=1; if(line[i]=='/') { // found closing tag while(line[i]!='>') i++; if(pretag.size()>(i-2)) // update tag tag = pretag.substr(0,pretag.size()-i+1); else tag = ""; } else { // found opening tag while(line[i]!=' ' && line[i]!='>') i++; tag = line.substr(1,i-1); // update tag if(pretag!="") tag = pretag + "." + tag; int j; while(line[i]!='>') { // go through attributes j = ++i; while(line[i]!=' ') i++; attr = line.substr(j,i-j); // attribute name while(line[i]!='\"') i++; j = ++i; while(line[i]!='\"') i++; value = line.substr(j,i-j); // attribute value i+= 1; tagMap[tag + "~" + attr] = value; } } createMap(--n, tag); } int main() { int n, q; cin >> n >> q; cin.ignore(); createMap(n,""); string attr, value; while(q--) { getline(cin,attr); value = tagMap[attr]; if(value=="") value = "Not Found!"; cout << value << endl; } return 0; }
Although the problem states "We can call an attribute by referencing the tag, followed by a tilde, '~' and the name of the attribute", there are queries without tilde (~) (test case #4, #5). So be careful when parsing your queries. I think the author should describe the problem more clear.
This problem is no-way a moderate one. Kinda hard and it falls to compilers knowledge and how lexical analysis and parsing really works. There is too much theory underlying this problem.
This one was definitely quite a bit more difficult than most of the others I've encounterd so far. Here's the solution I came up with. I tried to write an actual parser rather than just use regex. I'm somewhat happy with it, but I think there are probably some aspects that could use a bit of tidying up.
#include <iostream> #include <vector> enum node_type { tag, label, value }; struct parse_tree_node { node_type nt; std::string name; std::vector<struct parse_tree_node*> children; struct parse_tree_node* parent; }; void utility_free(struct parse_tree_node* ptn) { for(auto const& value: ptn->children) utility_free(value); delete ptn; } int main(void) { struct parse_tree_node* root = new struct parse_tree_node; struct parse_tree_node* current_level = root; current_level->name = "ROOT"; current_level->nt = tag; int n, q; std::cin >> n >> q; // parse lines into tree for(int i = 0; i < n; i++) { while(std::cin.get() != '<') ; if(std::cin.peek() != '/') { char next_char; bool expecting_space = true; bool need_next = false; bool done = false; bool quoted_mode = false; struct parse_tree_node* new_node = new struct parse_tree_node; new_node->nt = tag; current_level->children.push_back(new_node); new_node->parent = current_level; current_level = new_node; while(!done) { next_char = std::cin.get(); if(!quoted_mode) switch(next_char) { case '"': quoted_mode = true; need_next = true; break; case '>': done = true; break; case ' ': if(!expecting_space) need_next = true; break; case '=': { struct parse_tree_node* parent_node = new_node; new_node = new struct parse_tree_node; new_node->nt = value; parent_node->children.push_back(new_node); expecting_space = true; need_next = false; break; } default: if(need_next) { struct parse_tree_node* parent_node = current_level;; new_node = new struct parse_tree_node; new_node->nt = label; parent_node->children.push_back(new_node); need_next = false; } new_node->name.append(1, next_char); expecting_space = false; break; } else { if(next_char != '"') new_node->name.append(1, next_char); else quoted_mode = false; } } } else { current_level = current_level->parent; while(std::cin.get() != '>') ; } } // process queries for(int i = 0; i < q; i++) { struct parse_tree_node* current_level = root; std::string qstr_part; char peek_char; bool tilde_mode = false; while((peek_char = std::cin.peek()) == ' ' || peek_char == '\n') std::cin.get(); while(true) { char next_char = std::cin.get(); if(next_char == '.' || next_char == '~') { bool found = false; tilde_mode = next_char == '~'; for(auto const& value: current_level->children) if(value->nt == tag && value->name == qstr_part) { current_level = value; qstr_part = ""; found = true; break; } if(!found) { char drop_char; std::cout << "Not Found!" << std::endl; while((drop_char = std::cin.get()) != '\n' && drop_char != EOF) ; break; } } else if(next_char == '\n' || next_char == EOF) { bool found = false; if(tilde_mode) for(auto const& value: current_level->children) if(value->nt == label && value->name == qstr_part) { // This next line is a little sketchy. std::cout << value->children[0]->name << std::endl; found = true; break; } if(!found) std::cout << "Not Found!" << std::endl; break; } else { qstr_part.append(1, next_char); } } } utility_free(root); return 0; }
I was shocked when I read that most of you are using regex for this (wouldn't mind so much if the question gave any hint as to what it was even testing us on). My first instinct was to read the data into a tree of some sort, after all, isn't that how HTML is done in a browser? You guys have not shown any code- are you just reading the input into some uber long string and regexing that?!
In the end I have created a map of elements (just a struct), each containing a map of attrs and a map of inner elements, so it works like a linked list of sorts. Then I just have to traverse this. Made it sound quite simple, but it's been many hours of work (and revisions as the limited examples didn't help).
Bearing in mind the other challenges have taken anything from a few mins to half an hour at most, I'd like to join in with the people complaining this question needs re-wording or re-grading.
Sort 345 Discussions, By:
Please Login in order to post a comment