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

    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))
    Ответ написан