Как реализовать алгоритм рекурсией?

Question

[1Tima1]

Увидел вопрос - Как решить задачу с собеседования?
Задание понравилось, решил выполнить на Python.
Как оказалось,я настолько тупой, что не смог справится даже с одним заданием( хотя решать алгоритмы мне нравится)

spoiler

count = 0


def new_func(primer):
    numbers = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    count_str = ''
    if primer == '':
        return ''
    elif len(primer) == 1:
        return primer
    else:

        if primer[0] not in numbers and primer[0] != '(' and primer[0] != ')':
            return primer[0] + new_func(primer[1:])
        elif primer[0] in numbers:
            # не смог понять,этот блок нужен или все же нет
            if primer[1] != '(':
                return new_func(primer[1:])
            else:
                global count
                count += 1
                c = 0
                index = 0
                for k in range(len(primer)-1, 0, - 1):
                    if primer[k] == ')':
                        c += 1
                        if c == count:
                            index = k
                            break
                for j in range(int(primer[0])):
                    count_str += new_func(primer[2:index])
                    print(count_str)
                
                start_index = index+1
                
                if start_index + 1 == len(primer):
                    
                    return count_str + new_func('')
                else:
                    
                    return count_str + new_func(primer[start_index:])

Я что-то написал, но мне такое решение даже комментировать стыдно(((
Много часов просидел,исправляя одну логическую ошибку за другой.
Но уже нет сил.
На простом "3(c)" , он уже ломается.

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

Answer 1

[Wataru]

Нужна рекурсивная функция, которая обрабатывает строку и возвращает распакованную версию и где ее конец в заданной строке.

Ваша ошибка в том, что в слуае "2(с)3(a)" вы попытаетесь 2 раза повторить результат распаковки строки "с)3(a"

def process(s, begin):
  i = begin;
  ans = ""
  while i < len(s):
    // Внетренность скобок обрабатывается рекурсивно. ) - это конец строки для нас.
    if s[i] == ')': break;
    if '0' <= s[i] and s[i] <= '9':  // если встретили цифру
      k = 0
      // выделяем в k числовое значение записанного числа
      while i < len(s) and '0' <= s[i] and s[i] <= '9':
        // пока встречаются цифры берем их численное значение и приписываем в конец к k
        k = 10*k + ord(s[i]) - ord('0')
        i+=1
      // если после числа идет бува, то просто копируем ее нужное количетсво раз
      if  'a' <= s[i] and s[i] <= 'z': 
        ans += s[i:i+1]*k
        i+=1
      else:
        // иначе - должна быть скобка.
        assert(s[i] == '(')
        // рекурсивно обрабатываем внутренность скобок. Функция вернет нам, где
       // закрывающая скобка для данной.
        (i, cur) = process(s, i+1)
       // копируем результат распаковки строки внутри скобок нужное количетво раз
        ans += cur * k;
    else:
     // цирфы не было. Просто символ без множителя идет в ответ.
      assert('a' <= s[i] and s[i] <= 'z')
      ans += s[i:i+1]
      i += 1
  // мы могли закончить цикл на закрывающей скобке или в конце строки.
  // но скобку надо пропустить. Прибавляем 1 к счетчику.
  if i < len(s): i+=1
  return (i,ans)



print (process("abc", 0))
print (process("3a", 0))
print (process("3(a)", 0))
print (process("2(ab)", 0))
print (process("10(a)", 0))
print (process("2(b2(a))", 0))

Comments

[1Tima1]

if '0' <= s[i] and s[i] <= '9':

Вы сравниваете строки, так как будто это числа?

if 'a' <= s[i] and s[i] <= 'z':

что это за методы такие?

[1Tima1]

можете добавить хотя бы небольшие комментарии?

к примеру, зачем вам позиция в юникоде?

ord(s[i]) - ord('0')

у меня просто еще нет навыка, анализировать код,без комментариев.

[Wataru]

1Tima1,

По первому вопросу: s[i] - это i-ый символ в строке (считая с 0).

Сравнения там делаются чтобы отделить цифры от букв и от скобок. Вы у себя сморите, что символ один из numers, но можно это сделать сравнениями '0'<=s[i] and s[i] <= '9'. Сравнение строк же происходит посимвольно. Это не идеальный способ в питоне, возможно есть более корректный метод, я не питонист.

ord(s[i]) - ord('0') - должно выдвавть численное значение цифры. Для '7' - должно вернуть 7. Пользуется тем, что цифры идут в алфавите подряд с 0 до 9.

Важно отментить, что мой пример решения не работает с юникодом, а только c ascii текстом. Можно изменить так, чтобы работало не только с английским алфавитом. Для этого надо выделать в тексте только цифры и скобки, а все остальное считать текстом. Т.е. заменить проверку на то, чот символ от 'a' до 'z' проверкой что символ не цифра и не скобка.

Зато мое решение, в отличие от вашего, работает с многозначными числами и "123a" распакует именно как 123 копии "a", а не 1 копию "2" и 3 копии "a".

[Wataru]

1Tima1, Я отредактировал ответ, дописав комментарии в код. Но вроде все должно быть понятно и без них. Код довольно простой.

[Станислав Некрасов]

wataru,

ord(s[i]) - ord('0') == int(s[i])
('0' <= s[i] and s[i] <= '9') == ('0' <= s[i] <= '9') == s[i].isdigit() 
('a' <= s[i] and s[i] <= 'z') == ('a' <= s[i] <= 'z') == s[i].isalpha()
(i, cur) = process(s, i+1) => i, cur = process(s, i + 1)
s[i:i+1] == s[i]
return (i, ans) => return i, ans
assert (...) => assert ...
// ... => # ...

[Wataru]

Станислав Некрасов, не питонист я. Спасибо за комментарии.

[1Tima1]

1) если вы не питонист, то мне страшно подумать кто я тогда))
я понятия не имел, что существуют методы ord и assert
2)

Зато мое решение, в отличие от вашего, работает с многозначными числами и "123a" распакует именно как 123 копии "a", а не 1 копию "2" и 3 копии "a".

Зато мое решение, в отличие от вашего, работает...
Дальше можно было не писать :D

3)Как я понял из задания, цифры просто так стоять не могут, они должны быть перед скобками или буквой

[Wataru]

1Tima1, Если цифр нет подряд, то тогда вам не нужен цикл, в котором считается k. просто делайте вместо него

k = int(s[i])
i += 1

[Станислав Некрасов]

wataru, и 4 пробела вместо 2. Удачи)

[EternaLGreeD]

Wataru, Добрый день! Спасибо большое за решение, пытался решить аналогичную задачу правда на Java. Попробовал переписать алгоритм с python на java и понял, что для работы функции правильно нужно возвращать не только строку рекурсивно, но и позицию. Так вот, не могли бы подсказать как можно было бы переделать алгоритм, чтобы можно было обойтись возвратом одного значения?( Ведь в java нет возврата нескольких значений). Вроде бы несложно, но что-то не выходит. Заранее спасибо!

[Wataru]

EternaLGreeD, Можно возвращать часть значений через reference параметры.

Например, можно возвращать только индекс, а саму строку собирать в каком-то stringBuilder-е который передается в параметре. Так будет эффективнее всего.

Или создать новый класс с двумя значениями и возвращать его. Или использовать какой-то уже встроенный класс для группировки нескольких значений в один класс. Pair, например.

[EternaLGreeD]

Wataru, большое спасибо. Вариант с передачей ещё одного дополнительного параметра StringBuilder помимо i и s мне нравится. Попробую переделать. Если не сложно можете дать какой-то совет по изучению рекурсивных алгоритмов? Когда начинается рекурсия с ветвлением или же рекурсивные вызовы внутри цикла, голова кругом идёт.

[Wataru]

EternaLGreeD, Только один совет - сформулируйте четко в голове, а лучше вообще запишите - что делает функция. Какие параметры что означают, что за результат. Потом при написании все как-то понятнее. Вот пример из задачи. Функция распаковывет кусок строки начиная с заданного символа до выхода из текущего уровня скобок и возвращает, где текущий уровень кончается.

Когда есть такая формулировка - рекурсивные вызовы понятны. Вот просто символы мы циклом распаковываем, а если встречаем '(', то вызываемся рекурсивно. Так можно рассуждать о функции вообще не параясь о рекурсивных вызовах. Представьте, что в теле не рекурсивные вызовы, а вызвыается другая функция, которую даже не вы писали. Просто она что-то как-то делает. И вот ваша функция должна делать что-то опираясь на нее. не надо думать про дерево рекурсивных вызовов и т.д. Уже потом надо прикинуть, а когда рекурсия кончится, и что нельзя вызывать с теми же параметрами по кругу. Но обычно это все тривиально - какой-то параметр только уменьшается или увеличивается.

[EternaLGreeD]

Wataru, Спасибо еще раз за совет! Посидев 2 часа, что-то не вышло переделать, так чтобы возвращалось только int-овое значение позиции, а ответ собирать в 3 параметре метода. Но зато как-то быстро заработало с использованием дополнительного класса для возврата, где есть 2 поля (номер и текущая строка). Если вас не затруднит, не могли бы вы помочь со способом , где передается дополнительный reference параметр? Хоть и сделал одним способом, но перфекционизм не дает покоя :)

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

spoiler

public class UnpackStringNew {


    public static CurrentStringNew unpackString(String s, int begin){
        int i = begin;
        StringBuilder ans = new StringBuilder();
        while (i < s.length()){
            if (s.charAt(i) == ']') break;
            if( (s.charAt(i) >= '0') && (s.charAt(i)<='9')){
                int k =0;
                while ((i < s.length()) && (s.charAt(i) >= '0') && (s.charAt(i)<='9')){
                   k= 10*k + ((int) s.charAt(i) - (int) '0');
                   i++;
                }
                if ((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')){
                    char [] repeatedChar = new char[k];
                    Arrays.fill(repeatedChar,s.charAt(i));
                    ans.append(repeatedChar);
                    i++;
                } else if (s.charAt(i) == '['){
                    CurrentStringNew currentStringNew = unpackString(s, i + 1);
                    i = currentStringNew.Pos;
                    for (int j = 0; j < k; j++) {
                        ans.append(currentStringNew.currentStr);
                    }

                }

            } else {
                ans.append(s.charAt(i));
                i++;
            }
        }
        if (i < s.length()) i++;
        CurrentStringNew currentStringNew = new CurrentStringNew();
        currentStringNew.currentStr = ans;
        currentStringNew.Pos = i;
        return currentStringNew;
    }

    public static void main(String[] args) {
        CurrentStringNew s = unpackString("3[xyz]4[xy]z", 0);
        System.out.println(s.currentStr);
    }
}

class CurrentStringNew {
    int Pos;
    StringBuilder currentStr;
}

[Wataru]

EternaLGreeD, Ну передавайте StringBuilder третьим параметром. В main его создавайте и после вызова получайте из него строку.