1

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

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

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

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

4
  • 1
    добавь ссылку на задачу
    – Grundy
    2 фев в 18:42
  • Не помешает использовать стек (структура данных)
    – MBo
    2 фев в 19:23
  • @MBo, можно просто в цикле заменять начиная с внутренних скобок, пока замены не кончатся
    – Grundy
    2 фев в 19:34
  • непонятно, перед скобкой может быть только цифра или число
    – Grundy
    2 фев в 19:36

4 ответа 4

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();
}

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

1
1

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

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

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

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

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

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

1

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

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

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

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

1
  • Идти дальше по строке, пока не встретится закрывающая скобка. Запомнить ее индекс. - неверный шаг, так как если есть вложенные скобки - первой будет вложенная закрывающая скобка
    – Grundy
    2 фев в 22:15
0

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

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

4
  • 1
    Заодно тут можно узнать, что скрывается под загадочным словом algorithms
    – rotabor
    3 фев в 7:43
  • "От тебя хотят ...". Нет, не хотят. Сортировочная станция потребует много памяти, без неё будет и проще и быстрее. 3 фев в 10:16
  • @StanislavVolodarskiy Все предложенные здесь ответы реализуют этот алгоритм. С логической точки зрения использование стека и рекурсивный вызов функции - одно и то же.
    – rotabor
    3 фев в 11:06
  • @rotabor, я только упомянул что любые алгоритмы, которые следуют образцу сортировочной станции, перерасходуют память и иногда работают медленнее чем могли бы. Сортировочная станция - мощный универсальный алгоритм, вся мощность и универсальность которого не нужна для решения этой задачи. Да, других алгоритмов тут нет. Появятся. 3 фев в 11:11

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.