Расширение строки codewars

Question

Есть описание того что должно происходить со строкой после обработки

solve("3(ab)") = "ababab" -- because "ab" repeats 3 times

solve("2(a3(b))") = "abbbabbb" -- because "a3(b)" == "abbb", which repeats twice.

К описанию прилагается список тем которые надо знать чтобы решить эту задачу и там указано просто algorithms, но у меня что-то почти нет идей как такое решать, хотел бы чтобы подкинули идею как подступиться к задаче. Я думаю что надо идти по строке и как встретили цифру запомнить её, а затем считать содержимое скобок и повторить его в цикле предыдущие число раз, но как-то всё туманно у меня в голове

Answer 1

Вижу тут две операции:

повторить строку указанное число раз и
добавить символ в строку.

Причём операция 1 отложенная до закрытия скобки. Её нужно ложить в стек.

Создаём пустую строку str.
Цикл по символам строки. Берём очередной символ:

Если буква, то добавляем в str.
Если цифра, то идём до (. Если встретилась буква или конец строки, то это ошибка. Если дошли до (, то преобразуем цифры в число, кладём на стек str, потом число. Обнуляем str.
Если ), то берём число из стека и повторяем str указанное число раз. Если в стеке пусто, то ошибка. Берём из стека строку и добавляем её спереди к str.

Когда дошли до конца строки, то если стек пустой, то выдаём str как результат, если стек не пустой, то ошибка.

Answer 2

Можно пойти слева направо и каждое выражение в скобках решать как подзадачу.

Не совсем оптимальный пример работы со строками, но идея думаю понятна

string solve(string s)
{
    var ret = new StringBuilder();

    int ind = 0;
    // идем по строке слева направо
    while (ind < s.Length)
    {
        // если встретили цифру
        if (char.IsDigit(s[ind]))
        {
            // на случай еслт число двузначное, ищем конец числа и парсим
            int start = ind;
            while (char.IsDigit(s[ind])) ind++;

            var reps = int.Parse(s.Substring(start, ind - start));
            
            // после числа всегда идет открывающая скобка
            // ищем соответсвующую закрывающую
            int brackets = 1;
            start = ind;
            ind++;

            while (brackets != 0)
            {
                if (s[ind] == '(') brackets++;
                if (s[ind] == ')') brackets--;
                ind++;
            }
            
            // как нашли как нашли откр и закр скобки
            // для строки внутри скобок решаем подзадачу
            // то есть вызываем сами себя
            var rep = solve(s.Substring(start + 1, ind - start - 2));
            
            // ну и в результат добавляем подзадачу нужное количество раз
            for (int j = 0; j < reps; j++) ret.Append(rep);
        }
        else
        {
            // если на вхорде не число, значит символ, 
            // просто добаляем его в результат
            ret.Append(s[ind]);
            ind++;
        }
    }

    return ret.ToString();
}

Проверка

Console.WriteLine(solve("3(ab)"));
Console.WriteLine(solve("2(a3(b))"));

Результат

ababab
abbbabbb

UPD

Для конкретно этой каты задание не полное. Вот тесты, которые решение должно проходить

assertEquals("ababab",Solution.solve("3(ab)"));
assertEquals("abbbabbb",Solution.solve("2(a3(b))"));
assertEquals("bccbccbcc",Solution.solve("3(b(2(c)))"));      
assertEquals("kabaccbaccbacc",Solution.solve("k(a3(b(a2(c))))"));

Видно, что скобка может стоять и без числа. Потому решение немного переделал. Пришлось также использовать java, так как C# для этой задачи недоступен.

Решение на java имеет ту же концепцию, но с одной разницей - учитывается, что перед скобкой может не быть числа, потому множитель по умолчанию 1.

public static String solve(String s) {
    StringBuilder ret = new StringBuilder();

    int ind = 0;
    int reps = 1;
    while (ind < s.length()) {
        reps = 1;
        
        if (Character.isDigit(s.charAt(ind))) {
            int start = ind;
            while (Character.isDigit(s.charAt(ind))) ind++;
            reps = Integer.parseInt(s.substring(start, ind));
        }
        
        if (s.charAt(ind) == '(') {
            int brackets = 1;
            int start = ind;
            ind++;
            while (brackets != 0) {
                if (s.charAt(ind) == '(') brackets++;
                if (s.charAt(ind) == ')') brackets--;
                ind++;
            }
            String rep = solve(s.substring(start + 1, ind - 1));
            for (int j = 0; j < reps; j++) ret.append(rep);

        } else {
            ret.append(s.charAt(ind));
            ind++;
        }
    }

    return ret.toString();
}

Все проверки пройдены, ката успшно принята.

Answer 3

Вы правильно понимаете общую концепцию решения задачи: нужно идти по строке и, когда встречается цифра, запоминать ее, а затем считать содержимое скобок и повторять его нужное количество раз.

Один из способов подступиться к задаче - использовать рекурсию. Это позволит эффективно обрабатывать вложенные скобки, как во втором примере. Вот как это может выглядеть:

Идти по строке, пока не встретится цифра
Когда встретится цифра, запомнить ее и продолжать идти по строке, пока не встретится открывающая скобка. Запомнить ее индекс.
Идти дальше по строке, пока не встретится закрывающая скобка. Запомнить ее индекс.
Рекурсивно вызвать функцию для содержимого между этими скобками.
Вернуться к шагу 1 и повторить цикл для оставшейся части строки.

Этот алгоритм может быть немного сложным для понимания, если вы не знакомы с рекурсией, но в целом, это эффективный способ решения такого типа задач.

Answer 4

От тебя хотят реализации Алгоритма сортировочной станции Эдсгера нашего Дейкстры.

Учти, что операторы у тебя заданы неявно: между числом и буквой подразумевается умножение, между буквой и числом - сложение (конкатенация).

БЛОГ НА HUSL

Расширение строки codewars

Ответы (4 шт):