#python #string #algorithm #recursion
#python #строка #алгоритм #рекурсия
Вопрос:
Редактировать: Допустим, у меня есть строка вложенных круглых скобок следующим образом: ((AB) CD(E (FG)HI((J (K))L))) (предположим, что parantheses сбалансированы и заключают dproperly Как мне рекурсивно удалить первый набор полностью ЗАКРЫТЫХ parantheses каждого подмножества полностью закрытых круглых скобок?
Так что в этом случае было бы (ABCD(E(FG)HI(JK)) . (AB) станет AB, потому что (AB) является первым набором закрытых круглых скобок в наборе закрытых круглых скобок (от (AB) до K)), E также является первым элементом набора круглых скобок, но поскольку у него нет круглых скобок, ничего не меняется, а (J) равнопервый элемент в наборе ((J)K) и, следовательно, круглые скобки будут удалены.
Это похоже на построение дерева выражений, и до сих пор я анализировал его во вложенный список и думал, что могу рекурсивно проверить, является ли первый элемент каждого вложенного списка instance(type(list)), но я не знаю как?
Вложенный список выглядит следующим образом:
arr = [['A', 'B'], 'C', 'D', ['E', ['F', 'G'], 'H', 'I', [['J'], 'K']]]
Возможно, преобразовать его в:
arr = [A, B, C, D, [E, [F, G], H, I, [J, K]]
Есть ли лучший способ?
Комментарии:
1. Каков конечный результат, к которому вы стремитесь? Потому что, если вы продолжите это делать, вы получите строку без круглых скобок…. Чем это полезно для вас?
2. Что ж.. Я бы сказал , что результат будет выглядеть
['A','B', 'C', 'D',['E','F','G','H','I',['J', 'K']]следующим образом . Говоря, что мы начинаем с['J'], затем переходим к[['J'], 'K']и удаляем первые фигурные скобки, чтобы получить['J', 'K'], затем мы снова переключаемся на['E', ['F', 'G'], 'H', 'I', 'J', 'K']удаление первых .. и т. Д3. Исходя из формулировки, я бы согласился с @Nf4r. Кажется, я не могу следовать логике того, как получить ваш пример вывода..
4. Возможно, предполагается, что внутри каждой подстроки, заключенной в круглые скобки, если сама эта подстрока начинается с подстроки, заключенной в круглые скобки, круглые скобки должны быть удалены из этой внутренней подстроки. По сути, замена
(({1}){2}) -> ({1}{2}), за исключением того, что вместо простого удаления скобок из({1}), к тому же алгоритму следует рекурсивно применять({1}). Если это так, то в вопросе требуется более четкое описание.5. Это вопрос с подвохом? У вас есть 6 открывающих круглых скобок и только 5 закрывающих.
Ответ №1:
Если я правильно понял вопрос, эта уродливая функция должна сделать свое дело:
def rm_parens(s):
s2 = []
consec_parens = 0
inside_nested = False
for c in s:
if c == ')' and inside_nested:
inside_nested = False
consec_parens = 0
continue
if c == '(':
consec_parens = 1
else:
consec_parens = 0
if consec_parens == 2:
inside_nested = True
else:
s2.append(c)
s2 = ''.join(s2)
if s2 == s:
return s2
return rm_parens(s2)
s = '((AB)CD(E(FG)HI((J)K))'
s = rm_parens(s)
print(s)
Обратите внимание, что эта функция будет вызывать себя рекурсивно до тех пор, пока не исчезнут последовательные круглые скобки. Однако в вашем примере ((AB)CD(E(FG)HI((J)K)) для создания (ABCD(E(FG)HI(JK)) достаточно одного вызова.
Ответ №2:
Вам нужно свести свою логику к чему-то достаточно понятному для программирования. То, что я получаю из ваших объяснений, будет выглядеть как приведенный ниже код. Обратите внимание, что я не рассматривал крайние случаи: вам нужно будет проверить, нет ли элементов, попасть в конец списка и т. Д.
def simplfy(parse_list):
# Find the first included list;
# build a new list with that set of brackets removed.
reduce_list = []
for pos in len(parse_list):
elem = parse_list[pos]
if isinstance(elem, list):
# remove brackets; construct new list
reduce_list = parse_list[:pos]
reduce_list.extend(elem)
reduce_list.extend(parse_list[pos 1:]
# Recur on each list element
return_list = []
for elem in parse_list
if isinstance(elem, list):
return_list.append(simplfy(elem))
else:
return_list.append(elem)
return return_list