SeniorCodeOccasionalNot answered yet
Expand a bracket grammar (term)[N] into the resulting string
A string follows the grammar: a term is either lowercase letters, or (term)[N] meaning the bracketed term repeated N times, and terms concatenate. Expand the input into its final string. Assume the input is always valid.
Requirements:
Nmay be multi-digit and may be 0 (empty result for that term).- Example:
(a(b)[2])[3]expands toabbabbabb.
std::string expand(const std::string& s) {
// your code here
}Write the implementation.
Keep a stack of partial strings. On ( push the current string and start a fresh one; on ) parse the bracketed N, pop the saved string and append the just-built string repeated N times; otherwise append the letter. Multi-digit N parses digit by digit, N == 0 appends nothing.
- ✗Parsing only the first digit of a multi-digit count like
[28] - ✗Mishandling
N == 0, leaving stale characters instead of an empty term - ✗Trying a single accumulator, which breaks on nested brackets
- →How does this differ from the LeetCode
N[term]decode-string syntax? - →Could you expand lazily to avoid materialising a huge output string?
Contents
Task
Expand the nested bracket grammar (term)[N] into its final string.
Solution
#include <string>
#include <vector>
std::string expand(const std::string& s) {
std::vector<std::string> strStack;
std::string cur;
for (size_t i = 0; i < s.size(); ) {
char c = s[i];
if (c == '(') { strStack.push_back(cur); cur.clear(); ++i; }
else if (c == ')') {
++i; // skip '('
++i; // skip '['
int n = 0;
while (i < s.size() && isdigit(s[i])) // multi-digit N
n = n * 10 + (s[i++] - '0');
++i; // skip ']'
std::string repeated;
for (int k = 0; k < n; ++k) repeated += cur; // N == 0 → empty
cur = strStack.back() + repeated;
strStack.pop_back();
} else { cur += c; ++i; }
}
return cur;
}Key points
- A stack of strings restores the context around each term.
Nis parsed digit by digit;N == 0contributes nothing.- A single accumulator without a stack breaks on nested brackets.
Contents
