Created
August 4, 2021 14:28
-
-
Save afifabroory/6465e729b59dcdedb41780d7f9a2ede3 to your computer and use it in GitHub Desktop.
A parser for HRML (Custom Markup Language) - HackerRank
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* https://www.hackerrank.com/challenges/attribute-parser/ | |
*/ | |
#include <algorithm> | |
#include <cstdio> | |
#include <iostream> | |
#include <map> | |
#include <sstream> | |
#include <string> | |
#include <vector> | |
using namespace std; | |
#define endl "\n" | |
class HRMLParser { | |
private: | |
map<string, string> m; | |
string attrName, attrRelations; | |
int nElement, nQueries; | |
const string NOT_FOUND = "Not Found!"; | |
void createRelationship(stringstream& ss, string& tmpStr1, int& assignPos) { | |
while (ss >> tmpStr1) { | |
string::iterator tmpStrBegin = tmpStr1.begin(); | |
/** | |
* In some case attribute assigment doesn't separate by space | |
* so we need find first occurrence of "equal". | |
* If a string doesn't contains "equal" it will return constant npos | |
* | |
* COMMENT_ID: 1 | |
*/ | |
assignPos = tmpStr1.find_first_of('='); | |
// Store attribute value to map | |
if (assignPos != string::npos) { | |
/** | |
* From COMMENT_ID @1, if it's contains a "equal" | |
* then there is two possibility. | |
* | |
* 1) First possibility is only contains one character, namely "=" | |
* with length equal to 1. | |
* 2) Second possibility is contains other character/substr | |
* with length greater than 1. | |
* | |
* So, if a string in second possibility, then we need get rid | |
* other string we don't need. | |
* | |
* Becasue we already declare assignPos, | |
* we can reuse this variable instead write new statement to get length of char. | |
*/ | |
if (assignPos != 0) { | |
attrRelations += '~'; | |
attrRelations.append(tmpStr1.substr(0, assignPos)); | |
tmpStr1.erase(tmpStrBegin, tmpStrBegin+assignPos+1); | |
} else { | |
// If contains a single char "equal" then get next value of attribute | |
ss >> tmpStr1; | |
} | |
// Remove all double quotes and '>' in string | |
tmpStr1.erase( | |
remove(tmpStrBegin, tmpStr1.end(), '"'), tmpStr1.end() | |
); | |
tmpStr1.erase( | |
remove(tmpStrBegin+(tmpStr1.length()/2), tmpStr1.end(), '>'), tmpStr1.end() | |
); | |
// Insert attribute relationship and value into map. | |
m.insert(pair<string, string>(attrRelations, tmpStr1)); | |
attrRelations = attrName; | |
} else { | |
attrRelations += '~'; | |
attrRelations.append(tmpStr1); | |
} | |
} | |
} | |
public: | |
HRMLParser(int nElement, int nQueries) { | |
this->nElement = nElement; | |
this->nQueries = nQueries; | |
} | |
/** | |
* Parse element and insert element relationship inside map. | |
* '~' Indicate relationship between element and attribute (element itself). | |
* '.' Indicate relationship between attribute and attribute. | |
*/ | |
void parseElement() { | |
vector<string> elementVec; | |
string element; | |
do { | |
// We need getline() to read entire line! | |
getline(cin, element); | |
// We need to remove unwanted backspace left. | |
auto tmpStrBegin = element.begin(); | |
element.erase( | |
remove(tmpStrBegin, element.end(), '\t'), element.end() | |
); | |
// Check whether it's open attribute or close attribute. | |
if (element.substr(0, 2).compare("</") != 0) { | |
int assignPos; | |
// Get first whitespace occurrence position. | |
int whitespacePos = element.find_first_of(' '); | |
/** | |
* If whitespace doesn't found then it's possible an element, doesn't have attribute | |
*/ | |
if (whitespacePos == string::npos) whitespacePos = element.length()-1; | |
// Get first less than sign occurrence position. | |
int ltPos = element.find_first_of('<') + 1; | |
/** | |
* Get attribute name and erase attribute for further process. | |
*/ | |
attrName = element.substr(ltPos, whitespacePos-1); | |
elementVec.push_back(attrName); | |
element.erase(element.begin(), element.begin()+whitespacePos+1); | |
// Check whether if it's nested element at least one. | |
if (elementVec.size() > 1) { | |
vector<string>::iterator itBegin, itEnd; | |
itBegin = elementVec.begin(); | |
itEnd = elementVec.end(); | |
attrRelations.erase(); | |
for (; itBegin != itEnd; ++itBegin) { | |
attrRelations.append(*itBegin); | |
if ( itBegin != (itEnd-1)) attrRelations.append("."); | |
} | |
attrName = attrRelations; | |
} else { | |
attrRelations.append(attrName); | |
} | |
string tmpStr1; stringstream ss(element); | |
// Create relationship | |
createRelationship(ss, tmpStr1, assignPos); | |
} else { | |
elementVec.pop_back(); | |
attrRelations.clear(); | |
} | |
} while (--nElement > 0); | |
} | |
void query() { | |
string queries; | |
do { | |
getline(cin, queries); | |
auto queryResult = m.find(queries); | |
if (queryResult != m.end()) { | |
cout << queryResult->second << endl; | |
} else { | |
cout << NOT_FOUND << endl; | |
} | |
} while(--nQueries > 0); | |
} | |
}; | |
int main() { | |
ios_base::sync_with_stdio(false); | |
int nElement, nQueries; cin >> nElement >> nQueries >> ws; | |
HRMLParser HRML(nElement, nQueries); | |
HRML.parseElement(); | |
HRML.query(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment