План курса / Все задачи / Алгоритмы и структуры данных
Cкобочная грамматика
сложно
Дана строка s, представляющая выражение по скобочной грамматике:
(term)[n] — означает, что нужно повторить строку term n раз.
term может содержать строчные латинские буквы a-z, а также другие такие же конструкции (возможна вложенность).
Необходимо развернуть выражение и вернуть итоговую строку. Cкобочная структура всегда корректна.
Пример 1:
Ввод: s = "ab(cd)[2]"
Вывод: "abcdcd"
Пример 2:
Ввод: s = "x(yz)[3]w"
Вывод: "xyzyzyzw"
Пример 3:
Ввод: s = "a(b(c)[2])[3]"
Вывод: "abccbccbcc"
Ограничения:
len(s) >= 1
s содержит только символы латинского алфавита в нижнем регистре и числа
public class Solution
{
public static string BracketGrammar(string s)
{
List<string> stack = new List<string>();
string current = "";
foreach (char ch in s)
{
if (ch == '(')
{
// Сохраняем накопленную строку перед новой скобочной группой
stack.Add(current);
current = "";
}
else if (ch == ')')
{
// Завершили чтение скобочной группы — сохраняем её в стек
stack.Add(current);
current = "";
}
else if (ch == '[')
{
// Ждём число, ничего не делаем
continue;
}
else if (ch == ']')
{
// Закончили чтение числа — преобразуем current в число повторений
int repeatCount = int.Parse(current);
string str = stack[^1];
stack.RemoveAt(stack.Count - 1);
string repeated = string.Concat(Enumerable.Repeat(str, repeatCount));
string prefix = stack[^1];
stack.RemoveAt(stack.Count - 1);
current = prefix + repeated;
}
else
{
// Буква или цифра — просто добавляем к текущей строке
current += ch;
}
}
return current;
}
}
public class Solution
{
public static string BracketGrammar(string s)
{
List<string> stack = new List<string>();
string current = "";
foreach (char ch in s)
{
if (ch == '(')
{
// Сохраняем накопленную строку перед новой скобочной группой
stack.Add(current);
current = "";
}
else if (ch == ')')
{
// Завершили чтение скобочной группы — сохраняем её в стек
stack.Add(current);
current = "";
}
else if (ch == '[')
{
// Ждём число, ничего не делаем
continue;
}
else if (ch == ']')
{
// Закончили чтение числа — преобразуем current в число повторений
int repeatCount = int.Parse(current);
string str = stack[^1];
stack.RemoveAt(stack.Count - 1);
string repeated = string.Concat(Enumerable.Repeat(str, repeatCount));
string prefix = stack[^1];
stack.RemoveAt(stack.Count - 1);
current = prefix + repeated;
}
else
{
// Буква или цифра — просто добавляем к текущей строке
current += ch;
}
}
return current;
}
}
#include <string>
#include <vector>
using namespace std;
string bracketGrammar(string& s) {
vector<string> stack;
string current = "";
for (char ch : s) {
if (ch == '(') {
// сохраняем накопленную строку перед новой скобочной группой
stack.push_back(current);
current = "";
} else if (ch == ')') {
// завершили чтение скобочной группы — сохраняем её в стек
stack.push_back(current);
current = "";
} else if (ch == '[') {
// ждём число, ничего не делаем
continue;
} else if (ch == ']') {
// закончили чтение числа — преобразуем current в число повторений
int repeatCount = stoi(current);
string repeated = "";
for (int i = 0; i < repeatCount; ++i) {
repeated += stack.back();
}
stack.pop_back();
string prefix = stack.back();
stack.pop_back();
current = prefix + repeated;
} else {
// буква или цифра — просто добавляем к текущей строке
current += ch;
}
}
return current;
}
import java.util.*;
public class Solution {
public String bracketGrammar(String s) {
Stack<String> stack = new Stack<>();
StringBuilder current = new StringBuilder();
for (char ch : s.toCharArray()) {
if (ch == '(') {
// сохраняем накопленную строку перед новой скобочной группой
stack.push(current.toString());
current.setLength(0);
} else if (ch == ')') {
// завершили чтение скобочной группы — сохраняем её в стек
stack.push(current.toString());
current.setLength(0);
} else if (ch == '[') {
// ждём число, ничего не делаем
continue;
} else if (ch == ']') {
// закончили чтение числа — преобразуем current в число повторений
int repeatCount = Integer.parseInt(current.toString());
String str = stack.pop();
StringBuilder repeated = new StringBuilder();
for (int i = 0; i < repeatCount; i++) {
repeated.append(str);
}
String prefix = stack.pop();
current = new StringBuilder(prefix + repeated);
} else {
// буква или цифра — просто добавляем к текущей строке
current.append(ch);
}
}
return current.toString();
}
}
from typing import *
def bracket_grammar(s: str) -> str:
# стек для хранения промежуточных строк
stack = []
# аккумулятор для текущей подстроки
current = ''
for char in s:
if char == '(':
# сохраняем накопленную строку перед новой скобочной группой
stack.append(current)
current = ''
elif char == ')':
# завершили чтение скобочной группы — сохраняем её в стек
stack.append(current)
current = ''
elif char == '[':
# ждём число, ничего не делаем
continue
elif char == ']':
# закончили чтение числа — преобразуем current в число повторений
repeat_count = int(current)
# повторяем содержимое скобок
repeated = stack.pop() * repeat_count
# строка перед скобками
prefix = stack.pop()
# собираем всё вместе
current = prefix + repeated
else:
# буква или цифра — просто добавляем к текущей строке
current += char
return current
/**
* @param {string} s
* @returns {string}
*/
export function bracketGrammar(s) {
const stack = [];
let current = '';
for (const ch of s) {
if (ch === '(') {
// сохраняем накопленную строку перед новой скобочной группой
stack.push(current);
current = '';
} else if (ch === ')') {
// завершили чтение скобочной группы — сохраняем её в стек
stack.push(current);
current = '';
} else if (ch === '[') {
// ждём число, ничего не делаем
continue;
} else if (ch === ']') {
// закончили чтение числа — преобразуем current в число повторений
const repeatCount = parseInt(current);
const str = stack.pop();
const repeated = str.repeat(repeatCount);
const prefix = stack.pop();
current = prefix + repeated;
} else {
// буква или цифра — просто добавляем к текущей строке
current += ch;
}
}
return current;
}