SeniorКодИногдаЕщё не отвечали
Развернуть скобочную грамматику (term)[N] в строку
Строка задана грамматикой: term — это либо строчные буквы, либо (term)[N], что означает терм в скобках, повторённый N раз; термы конкатенируются. Разверните вход в итоговую строку. Считайте вход всегда корректным.
Требования:
Nможет быть многозначным и может быть 0 (пустой результат для этого терма).- Пример:
(a(b)[2])[3]разворачивается вabbabbabb.
std::string expand(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Держим стек частичных строк. На ( кладём текущую строку и начинаем новую; на ) разбираем N в скобках, снимаем сохранённую строку и дописываем собранную, повторённую N раз; иначе дописываем букву. Многозначное N разбирается поразрядно, N == 0 ничего не дописывает.
- ✗Разбирать только первую цифру многозначного счётчика вроде
[28] - ✗Неверно обрабатывать
N == 0, оставляя лишние символы вместо пустого терма - ✗Пытаться обойтись одним накопителем, что ломается на вложенных скобках
- →Чем это отличается от синтаксиса
N[term]в decode-string на LeetCode? - →Можно ли разворачивать лениво, чтобы не материализовать огромную строку вывода?
Оглавление
Задача
Разверните скобочную грамматику (term)[N] с вложенностью в итоговую строку.
Решение
#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; // пропускаем '('
++i; // пропускаем '['
int n = 0;
while (i < s.size() && isdigit(s[i])) // многозначное N
n = n * 10 + (s[i++] - '0');
++i; // пропускаем ']'
std::string repeated;
for (int k = 0; k < n; ++k) repeated += cur; // N == 0 → пусто
cur = strStack.back() + repeated;
strStack.pop_back();
} else { cur += c; ++i; }
}
return cur;
}Ключевые моменты
- Стек строк восстанавливает контекст вокруг каждого терма.
Nразбирается поразрядно;N == 0даёт пустой вклад.- Один накопитель без стека ломается на вложенных скобках.
Оглавление
