This challenge works with a custom-designed markup language HRML. In HRML, each element consists of a starting and ending tag, and there are attributes associated with each tag. Only starting tags can have attributes. We can call an attribute by referencing the tag, followed by a tilde, ‘~‘ and the name of the attribute. The tags may also be nested.
The opening tags follow the format:
<tag-name attribute1-name = "value1" attribute2-name = "value2" ...>
The closing tags follow the format:
</tag-name>
The attributes are referenced as:
tag1~value
tag1.tag2~nameGiven the source code in HRML format consisting of N lines, answer Q queries. For each query, print the value of the attribute specified. Print “Not Found!” if the attribute does not exist.
Example
HRML listing
<tag1 value = "value">
<tag2 name = "name">
<tag3 another="another" final="final">
</tag3>
</tag2>
</tag1>
Queries
tag1~value
tag1.tag2.tag3~name
tag1.tag2~value
Here, tag2 is nested within tag1, so attributes of tag2 are accessed as tag1.tag2~<attribute>. Results of the queries are:
Query Value tag1~value "value" tag1.tag2.tag3~name "Not Found!" tag1.tag2.tag3~final "final"
Input Format
The first line consists of two space separated integers, N and Q. N specifies the number of lines in the HRML source program. Q specifies the number of queries.
The following N lines consist of either an opening tag with zero or more attributes or a closing tag. There is a space after the tag-name, attribute-name, ‘=’ and value.There is no space after the last value. If there are no attributes there is no space after tag name.
Q queries follow. Each query consists of string that references an attribute in the source program. More formally, each query is of the form tagi1 . tagi2 . tagi3 . . . . tagim ~ attr = name where m >= 1 and tagi1 . tagi2 . tagi3 . . . . tagim are valid tags in the input.
Constraints
- 1 ≤ N ≤ 20
- 1 ≤ Q ≤ 20
- Each line in the source program contains, at most, 200 characters.
- Every reference to the attributes in the Q queries contains at most 200 characters.
- All tag names are unique and the HRML source program is logically correct, i.e. valid nesting.
- A tag can may have no attributes.
Output Format
Print the value of the attribute for each query. Print “Not Found!” without quotes if the attribute does not exist.
Sample Input
4 3
<tag1 value = "HelloWorld">
<tag2 name = "Name1">
</tag2>
</tag1>
tag1.tag2~name
tag1~name
tag1~valueSample Output
Name1
Not Found!
HelloWorldSolution Implementation
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
bool checkEnd(string name, string end) {
name = "</" + name + ">";
if (name == end) return true;
return false;
}
string nameTag(string demo) {
int from = demo.find_first_of('<');
int off = fmin(demo.find_first_of(' '), demo.find_first_of('>')) - 1;
return demo.substr(from + 1, off);
}
struct range {
int from;
int to;
};
range rangeOfTag(string tags, string nameTag, int index = 0) {
range result;
result.from = 0;
result.to = 0;
string endTag = "</" + nameTag + ">";
nameTag = "<" + nameTag;
unsigned long int j = 0, k = 0;
for (unsigned long int i = index; i < tags.length(); i++) {
if (tags[i] == nameTag[j]) {
++j;
if (j == nameTag.length()) {
result.from = i - j + 1;
}
}
else
j = 0;
if (tags[i] == endTag[k]) {
++k;
if (k == endTag.length()) {
result.to = i - k + 1;
}
}
else
k = 0;
}
return result;
}
int indexEnd(string tags, string name) {
int j = 0;
for (int i = 0; i < tags.length(); i++) {
if (tags.at(i) == name.at(j)) {
++j;
if (j == name.length()) {
return i - j;
}
}
}
return 0;
}
string solve(string tags, string querie, int index) {
if (index < 0) return "Not Found!";
string temp = "";
string att;
range correct;
correct.from = index;
correct.to = index;
while (tags[correct.from] != ' ') --correct.from;
while (tags[correct.to] != ' ') ++correct.to;
vector<string> split;
string name = tags.substr(correct.from + 1, correct.to - correct.from - 1);
string templateS = "";
for (int i = 0; i < tags.length(); i++) {
if (tags.at(i) == '<') {
string temp = tags.substr(i + 1, fmin(tags.find('>', i + 1), tags.find(' ', i + 1)) - i - 1);
range ran = rangeOfTag(tags, temp);
if (ran.from < index && ran.to > index) {
templateS = templateS + temp + '.';
}
}
}
templateS[templateS.length() - 1] = '~';
templateS = templateS + name;
string result = tags.substr(tags.find('"', index) + 1, tags.find('"', tags.find('"', index) + 1) - tags.find('"', index) - 1);
if (querie == templateS) return result;
return "Not Found!";
}
int main() {
int n, q;
cin >> n >> q;
cin.ignore(1, 'n');
map<string, string> tags;
string title, temp = "";
bool check = true;
for (int i = 0; i < n; i++) {
string temp1;
getline(cin, temp1);
if (check) {
title = nameTag(temp1);
check = false;
}
temp = temp + temp1;
if (checkEnd(title, temp1)) {
tags[title] = temp;
temp = "";
check = true;
}
}
for (int i = 0; i < q; i++) {
string querie;
cin >> querie;
int j = 0;
string title = "";
while (!ispunct(querie.at(j)) && j < querie.length()) {
title = title + querie.at(j);
j++;
}
if (tags.find(title) != tags.end()) {
int check = querie.find('~');
if (check) {
string nameAttri = querie.substr(querie.find('~') + 1, querie.length() - querie.find('~'));
int index = tags[title].find(nameAttri);
string demo = solve(tags[title], querie, index);
while (index >= 0) {
if (demo != "Not Found!") break;
index = tags[title].find(nameAttri, index + nameAttri.length() + 1);
demo = solve(tags[title], querie, index);
}
cout << demo << endl;
}
else cout << "Not Found!";
}
else
{
cout << "Not Found!" << endl;
}
}
return 0;
}