How to implement a recursive algorithm?

Question

Python

I saw the question - How to solve the problem from the interview?
I liked the task, I decided to do it in Python.
As it turned out, I'm so dumb that I couldn't even cope with one task (although I like solving algorithms)

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:])

I wrote something, but I'm even ashamed to comment on such a decision (((
I spent many hours correcting one logical error after another.
But I no longer have the strength.
On a simple "3 (c)", it already breaks.

I ask you to help finish this algorithm so that there is no feeling that I spent several hours not ineffective code

Answer 1

Need a recursive function that processes a string and returns the unpacked version and where it ends in the given string.
Your mistake is that in the case "2(c)3(a)" you will try to repeat the result of unpacking the string "c)3(a" 2 times

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))