@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)" , он уже ломается.

Я прошу вас помочь закончить этот алгоритм, чтобы не было чувства что я потратил несколько часов не безрезультатный код
  • Вопрос задан
  • 144 просмотра
Решения вопроса 1
wataru
@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))
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы