In this HackerRank Attribute Parser problem in c++ we have given 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.

HackerRank Attribute Parser in C++ problem solution


HackerRank Attribute Parser in C++ problem solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

struct tag;

typedef std::map<std::string, tag*> tagmap;
typedef std::map<std::string, std::string> ssmap;

struct tag {
	tag() : parent(0), name() {};
	tag(tag* p, string& s) : parent(p), name(s) {};
	tag* parent;
	string name;
	ssmap attributes;
	tagmap children;
};

#define f(i,s,e) for(int i=s;i<e;++i)

int parse_attributes(char * sline, int x, tag* Context)
{
	int state = 0;
	int sp = 0;
	std::string attrname;
	while (sline[x] != 0) {
		if (state == 0) {
			if (sline[x] == '>' || sline[x] == '/') {
				++x; state = 100;
			} else if (sline[x] == ' ' || sline[x] == '\t') { 
				++x; 
			}
			else {
				sp = x;
				state = 1;
			}
		}
		else if (state == 1) {
			if (sline[x] == '>' || sline[x] == '/') {
				++x; state = 100;
			} else if (sline[x] != ' ' && sline[x] != '\t' && sline[x] != '=') {
				++x;
			}
			else {
				state = (sline[x] == '=') ? 3 : 2;
				sline[x] = 0;
				attrname = sline + sp;
				sp=++x;
			}
		}
		else if (state == 2) {
			if (sline[x] == '>' || sline[x] == '/') {
				++x; state = 100;
			}
			else if (sline[x] != '=') {
				++x;
			}
			else {
				state = 3;
				sp = ++x;
			}
		}
		else if (state == 3) {
			if (sline[x] == '>') {
				++x; state = 100;
			}
			else if (sline[x] == '\"') {
				sp = ++x;
				state = 6;
			} else {
				++x;
			}
		}
		else if (state == 6) {
			if (sline[x] == '\"') {
				sline[x] = 0;
				Context->attributes[attrname] = sline + sp;
				sp = ++x;
				state = 0;
			}
			else {
				++x;
			}
		}
		else if (state == 100) {
			break;
		}
	}
	return x;
};

void parse_query(char * sline, tag* Context) {
	int x = 0;
	int state = 0;
	int sp = 0;
	std::string name;
	while (sline[x] != 0) {
		if (state == 0) {
			if (sline[x] != ' ' && sline[x] != '\t') {
				sp = x;
				state = 1;
			}
			else {
				++x;
			}
		}
		else if (state == 1) {
			if (sline[x] == ' ' || sline[x] == '\t' || sline[x] == '.' || sline[x] == '~') {
				if (sline[x] == ' ' || sline[x] == '\t') {
					state = 2;
				}
				else if (sline[x] == '.') {
					state = 0;
				}
				else if (sline[x] == '~') {
					state = 3;
				}
				sline[x] = 0;
				++x;
				name = sline + sp;
				tagmap::iterator itr = Context->children.find(name);
				if (itr != Context->children.end()) {
					Context = itr->second;
				}
				else {
					cout << "Not Found!" << endl;
					return;
				}
			}
			else {
				++x;
			}
		}
		else if (state == 2) {
			if (sline[x] == '.') { 
				++x;
				state = 0;
			}
			if (sline[x] == '~') {
				++x;
				state = 3;
			}
			else {
				++x;
			}
		}
		else if (state == 3) {
			if (sline[x] != ' ' && sline[x] != '\t') {
				sp = x;
				state = 4;
			}
			else {
				++x;
			}
		}
		else if (state == 4) {
			if (sline[x] == ' ' || sline[x] == '\t') {
				sline[x] = 0;
				name = sline + sp;
				ssmap::iterator itr = Context->attributes.find(name);
				if (itr != Context->attributes.end()) {
					cout << itr->second.c_str() << endl;
					return;
				}
				else {
					cout << "Not Found!" << endl;
					return;
				}
			}
			else {
				++x;
			}
		}
	}
	if (state == 4){
		name = sline + sp;
		ssmap::iterator itr = Context->attributes.find(name);
		if (itr != Context->attributes.end()) {
			cout << itr->second.c_str() << endl;
			return;
		}
		else {
			cout << "Not Found!" << endl;
			return;
		}
	}
	else {
		cout << "Not Found!" << endl;
		return;
	}
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
	char * sline = new char[2000];
	gets(sline);
	int N, Q;
	sscanf(sline, "%d %d", &N, &Q);
	tag* DOM = new tag();
	tag* Context = DOM;
	f(i, 0, N) {
		gets(sline);
		int x = 0;
		int sp = 0;
		while (sline[x] != 0) {
			if (sline[x] == '<'){
				++x;
				if (sline[x] == '/') {
					sp = ++x;
					while (sline[x] != ' ' && sline[x] != '\t' && sline[x] != '>' && sline[x] != 0) { ++x; }
					if (sline[x] == 0) break;
					sline[x] = 0;
					tag* CP = Context;
					while (CP) {
						if (CP->name != sline + sp) { CP = CP->parent; }
						else break;
					}
					if (CP != 0) {
						Context = CP->parent;
					}
					//break;
				}
				else {
					sp = x;
					++x;
					while (sline[x] != ' ' && sline[x] != '\t' && sline[x] != '/' && sline[x] != '>' && sline[x] != 0) { ++x; }
					bool na = false;
					if (sline[x] == 0) break;
					if (sline[x] == '/' || sline[x] == '>') {
						na = true;
					}
					sline[x] = 0;
					string nm = sline + sp;
					tagmap::iterator itr = Context->children.find(nm);
					if (itr != Context->children.end()) {
						Context = itr->second;
					}
					else {
						Context = Context->children[nm] = new tag(Context, nm);
					}
					if (!na) {
						x = parse_attributes(sline, x + 1, Context);
						//break;
					}
					else {
						++x;
					}
				}
			}
			else {
				++x;
			}
		}
	}

	f(i, 0, Q) {
		gets(sline);
		parse_query(sline, DOM);
	}
    return 0;
}