Overveiw
This article discusses several classic simulation problems that involve network string processing. Each problem requires parsing structured text, handling patterns, and implementing matching or replacement logic. The solution are written in C++ using standard libraries.
Template Generation System
The first problem involves a template engine that replaces {{ variable }} placeholders with actual values. Variables are stored in an std::unordered_map. The input consists of n template lines and m variable definitions. Each variable is a key-value pair where the value is enclosed in double quotes. The algorithm scans each template line chraacter by character: when it encounters {{, it extracts the key until }}, looks it up in the map, and prints the corresponding value; otherwise it outputs the character as is.
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
cin.ignore(); // skip newline after n m
vector<string> templates;
while (n--) {
string line;
getline(cin, line);
templates.push_back(line);
}
unordered_map<string, string> vars;
while (m--) {
string key, value;
cin >> key;
char ch;
while ((ch = getchar()) != '\"'); // skip to opening quote
while ((ch = getchar()) != '\"') value += ch;
vars[key] = value;
}
for (const auto &line : templates) {
for (size_t i = 0; i < line.size(); ) {
if (i + 1 < line.size() && line[i] == '{' && line[i+1] == '{') {
size_t j = i + 3;
string key;
while (!(line[j] == ' ' && line[j+1] == '}' && line[j+2] == '}')) {
key += line[j++];
}
cout << vars[key];
i = j + 3;
} else {
cout << line[i++];
}
}
cout << endl;
}
return 0;
}
Markdown Parsing
This problem simulates a Markdown-to-HTML converter. It handles inline elements: emphasis (underscore) and links (square brackets), and block-level elements: headers (#), unordered lists (*), and paragraphs. The input is read line by line; consecutive non-empty lines are grouped. For each group, the type is determined by the first character: # for headings, * for unordered lists, otherwise a paragraph.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> lines;
// Process inline link starting at position i; returns new index after closing ')'
int handleLink(const string &s, int i) {
string text, url;
for (i++; s[i] != ']'; i++) {
char c = s[i];
if (c == '_') {
text += "<em>";
i++;
while (s[i] != '_') text += s[i++];
text += "</em>";
} else {
text += c;
}
}
for (i += 2; s[i] != ')'; i++) url += s[i];
printf("<a href=\"%s\">%s</a>", url.c_str(), text.c_str());
return i;
}
// Process inline emphasis starting at position i; returns new index after closing '_'
int handleEmphasis(const string &s, int i) {
printf("<em>");
for (i++; s[i] != '_'; i++) {
if (s[i] == '[') i = handleLink(s, i);
else putchar(s[i]);
}
printf("</em>");
return i;
}
// Process a single line within a block (strip leading spaces first)
void processInline(const string &raw) {
int k = 0;
while (k < (int)raw.size() && raw[k] == ' ') k++;
string str = raw.substr(k);
for (int i = 0; i < (int)str.size(); i++) {
if (str[i] == '_') i = handleEmphasis(str, i);
else if (str[i] == '[') i = handleLink(str, i);
else putchar(str[i]);
}
}
// Render a block from line a to b (inclusive)
void renderBlock(int a, int b) {
string first = lines[a];
if (first[0] == '#') {
int level = 0;
while (first[level] == '#') level++;
printf("<h%d>", level);
processInline(first.substr(level));
printf("</h%d>\n", level);
} else if (first[0] == '*') {
puts("<ul>");
for (int i = a; i <= b; i++) {
printf("<li>");
processInline(lines[i].substr(1));
printf("</li>\n");
}
puts("</ul>");
} else {
printf("<p>");
for (int i = a; i <= b; i++) {
processInline(lines[i]);
if (i != b) cout << endl;
}
printf("</p>\n");
}
}
int main() {
string line;
while (getline(cin, line)) lines.push_back(line);
for (int i = 0; i < (int)lines.size(); i++) {
if (lines[i].empty()) continue;
int j = i + 1;
while (j < (int)lines.size() && !lines[j].empty()) j++;
renderBlock(i, j - 1);
i = j - 1;
}
return 0;
}
JSON Query
This problem requires parsing a JSON object (which may contain nested objects and string values) and answering queries using dot‑separated keys. The JSON input is flat (no spaces inside strings), and we use a recursive descent parser. We build a tree of objects (Obj) where each node can be a string or a dictionary of sub‑objects. Queries are split by . and traversed down the tree.
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
struct Node {
int type; // 1 = string, 2 = object
string val;
map<string, Node> children;
Node() {}
Node(const string &s) : type(1), val(s) {}
};
// Parse a JSON string from position k (opening quote assumed)
string parseString(const string &json, int &k) {
k++; // skip opening quote
string res;
while (json[k] != '\"') {
if (json[k] == '\\') {
res += json[k+1];
k += 2;
} else {
res += json[k++];
}
}
k++; // skip closing quote
return res;
}
// Forward declaration
Node parseObject(const string &json, int &k);
// Parse a key-value pair and add to node
void parsePair(Node &node, const string &json, int &k) {
string key = parseString(json, k);
while (json[k] != ':') k++;
k++; // skip ':'
while (json[k] != '\"' && json[k] != '{') k++;
if (json[k] == '\"')
node.children[key] = Node(parseString(json, k));
else
node.children[key] = parseObject(json, k);
}
Node parseObject(const string &json, int &k) {
Node obj;
obj.type = 2;
while (json[k] != '{') k++;
k++; // skip '{'
while (json[k] != '}') {
if (json[k] == '\"')
parsePair(obj, json, k);
else
k++;
}
k++; // skip '}'
return obj;
}
void query(const Node &root, const vector<string> &keys) {
Node cur = root;
for (const auto &k : keys) {
if (cur.type == 1 || cur.children.find(k) == cur.children.end()) {
puts("NOTEXIST");
return;
}
cur = cur.children[k];
}
if (cur.type == 1)
printf("STRING %s\n", cur.val.c_str());
else
puts("OBJECT");
}
int main() {
int n, m;
cin >> n >> m;
cin.ignore();
string input, line;
while (n--) {
getline(cin, line);
input += line;
}
int pos = 0;
Node root = parseObject(input, pos);
while (m--) {
getline(cin, line);
vector<string> keys;
for (int i = 0; i < (int)line.size(); i++) {
int j = i + 1;
while (j < (int)line.size() && line[j] != '.') j++;
keys.push_back(line.substr(i, j - i));
i = j;
}
query(root, keys);
}
return 0;
}
URL Mapping
Implement a simple URL router. Rules are given in order; each rule contains a pattern (which may include <str>, <int>, <path>) and a name. When a request URL arrives, we try each rule in order. We split both the rule pattern and the URL by slashes and compare segment by segment, handling parameter types appropriately. <int> matches only digits (leading zeros removed), <str> matches any non‑slash string, and <path> matches the rest of the URL (including slashes).
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 110;
struct Rule {
string pattern, name;
} rules[MAXN];
int n, m;
// Remove leading zeros from a numeric string (if only zeros keep one zero)
string normalizeInt(const string &s) {
string t;
for (char c : s) if (isdigit(c)) t += c;
if (t.empty()) return "";
int idx = 0;
while (idx + 1 < (int)t.size() && t[idx] == '0') idx++;
return t.substr(idx);
}
// Attempt to match a URL against a pattern; returns empty vector on failure
vector<string> match(const string &pat, const string &url) {
vector<string> params = {""}; // dummy first element (name will be added later)
int i = 1, j = 1; // skip leading '/'
while (i < (int)pat.size() && j < (int)url.size()) {
int u = i + 1, v = j + 1;
while (u < (int)pat.size() && pat[u] != '/') u++;
while (v < (int)url.size() && url[v] != '/') v++;
string segPat = pat.substr(i, u - i);
string segUrl = url.substr(j, v - j);
if (segPat == "<str>") {
params.push_back(segUrl);
i = u + 1; j = v + 1;
} else if (segPat == "<int>") {
string num = normalizeInt(segUrl);
if (num.empty()) { params.clear(); return params; }
params.push_back(num);
i = u + 1; j = v + 1;
} else if (segPat == "<path>") {
params.push_back(url.substr(j));
return params;
} else {
if (segPat != segUrl) { params.clear(); return params; }
i = u + 1; j = v + 1;
}
}
// Both must end at the same time
if (i != (int)pat.size() || j != (int)url.size()) params.clear();
return params;
}
void handle(const string &url) {
for (int i = 0; i < n; i++) {
auto res = match(rules[i].pattern, url);
if (!res.empty()) {
cout << rules[i].name;
for (int k = 1; k < (int)res.size(); k++)
cout << ' ' << res[k];
cout << endl;
return;
}
}
puts("404");
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> rules[i].pattern >> rules[i].name;
while (m--) {
string url; cin >> url; handle(url);
}
return 0;
}
CSS Element Selector
The last problem is a simplified CSS selector. The input is a structured document where each line represents an element: indentation (two dots per level) indicates nesting, and an optional #id suffix. We need to answer queries: a tag selector (e.g., p), an id selector (e.g., #main), or a descendant selector (e.g., div p). We first parse the document into a tree (or keep a flat list with parent pointers). For each query, we split by spaces to get a sequence of selectors. We then check every element: for the first selector, we find matching elements; then for each subsequent selector, we filter those that have an ancestor matching the next selector. The output is the line numbers of the final matching elements.
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
struct Element {
int line; // 1-indexed line number
int depth; // number of '..' prefix
string tag; // lowercased tag
string id; // id (if any)
int parent; // index in element list
};
vector<Element> elems;
int main() {
int n, m;
cin >> n >> m;
cin.ignore();
// Parse document
for (int i = 1; i <= n; i++) {
string raw;
getline(cin, raw);
int depth = 0;
while (depth < (int)raw.size() && raw[depth] == '.') depth += 2; // each level = two dots
string content = raw.substr(depth);
Element e;
e.line = i;
e.depth = depth / 2;
// parse tag and optional id
string tag, id;
size_t pos = content.find(' ');
if (pos != string::npos) {
tag = content.substr(0, pos);
id = content.substr(pos + 1);
if (!id.empty() && id[0] == '#') id = id.substr(1);
} else {
tag = content;
}
for (char &c : tag) c = tolower(c);
e.tag = tag;
e.id = id;
// find parent: nearest previous element with depth == e.depth - 1
e.parent = -1;
for (int j = (int)elems.size() - 1; j >= 0; j--) {
if (elems[j].depth == e.depth - 1) {
e.parent = j;
break;
}
}
elems.push_back(e);
}
// Process queries
while (m--) {
string query;
getline(cin, query);
// split by spaces (selectors)
vector<string> parts;
stringstream ss(query);
string part;
while (ss >> part) parts.push_back(part);
// start with all elements matching the last selector? Actually we need descending matching.
// We'll collect candidate indices that match the entire chain.
vector<int> result;
for (int idx = 0; idx < (int)elems.size(); idx++) {
// check if this element matches the last selector in the chain
const Element &cur = elems[idx];
string lastSel = parts.back();
bool lastMatch = false;
if (lastSel[0] == '#') {
lastMatch = (cur.id == lastSel.substr(1));
} else {
string low = lastSel;
for (char &c : low) c = tolower(c);
lastMatch = (cur.tag == low);
}
if (!lastMatch) continue;
// now walk backwards through ancestors to match preceding selectors
int ancestorIdx = idx;
bool ok = true;
for (int p = (int)parts.size() - 2; p >= 0; p--) {
// find an ancestor that matches parts[p]
int par = elems[ancestorIdx].parent;
bool found = false;
while (par != -1) {
const Element &anc = elems[par];
bool match = false;
if (parts[p][0] == '#') {
match = (anc.id == parts[p].substr(1));
} else {
string low = parts[p];
for (char &c : low) c = tolower(c);
match = (anc.tag == low);
}
if (match) {
found = true;
ancestorIdx = par;
break;
}
par = anc.parent;
}
if (!found) { ok = false; break; }
}
if (ok) result.push_back(cur.line);
}
cout << result.size();
for (int l : result) cout << ' ' << l;
cout << endl;
}
return 0;
}