括弧が複数階層の文字列の階層ごとに分割したい

Question

前提・実現したいこと

次のようになっているものを，全て分割したいです。
input
((((AAA,BBB),CCC)DDD), (EEE,FFF))
output
(AAA,BBB)
((AAA,BBB),CCC)
(((AAA,BBB),CCC),DDD)
(EEE,FFF)
((((AAA,BBB),CCC)DDD), (EEE,FFF))

試したこと

一番小さい括弧は取れました。
そのあと大きくしていく方法がわかりません。
そして，テストデータは括弧が最大4個ですが，n階層になっても大丈夫なようにしたいです。
よろしくお願いします。

該当のソースコード

python3
import re

A = "((((AAA,BBB),CCC)DDD), (EEE,FFF))"
B = re.findall("([^()]+)",A)

for i in B:
print(i)

(AAA,BBB)
(EEE,FFF)

Answer 1

入力文字列を先頭から順にスキャンして:

• 開きカッコだった場合

→ スタックに位置を記憶しておく(これが文字列切り出しの開始位置になる)

• 閉じカッコだった場合

→ スタックから対応する開きカッコの位置を取り出して、そこから現在位置までの文字列を切り出す

というアプローチではどうでしょうか。

s = '((((AAA,BBB),CCC),DDD), (EEE,FFF))'

stack = []
result = []
for i, ch in enumerate(s):
    if ch == '(':
        stack.append(i)
    elif ch == ')':
        result.append(s[stack.pop():i + 1])

print(*result, sep='\n')

# (AAA,BBB)
# ((AAA,BBB),CCC)
# (((AAA,BBB),CCC),DDD)
# (EEE,FFF)
# ((((AAA,BBB),CCC),DDD), (EEE,FFF))

Comments

[contact2093]

一番簡潔だったので，こちらを採用しました。ありがとうございました。

Answer 2

再帰的にn階層たどるような場合、正規文法では表せず、文脈自由文法が要ります（チョムスキー階層より）。

適当に文法の定義っぽいものを書いて考えてみます。

node: "(" (node | symbol) "," (node | symbol) ")"
symbol: "[A-F]{3}"

みるからにLL(1)の文法です。簡単そうなので再帰下降構文解析で書いてみることにします。

src = "((((AAA,BBB),CCC),DDD),(EEE,FFF))"
p = 0

def node_p_():
    global p
    p += 1
    if src[p] == "(":
        e1 = node_p_()
    else:
        e1 = symbol_p_()
    p += 1
    if src[p] == "(":
        e2 = node_p_()
    else:
        e2 = symbol_p_()
    p += 1
    node =  (e1, e2)
    print(repr_node(node))
    return node

def symbol_p_():
    global p
    p += 3
    return src[p-3:p]

def repr_node(node):
    r = "("
    if isinstance(node[0], str):
        r += node[0]
    else:
        r += repr_node(node[0])
    r += ","
    if isinstance(node[1], str):
        r += node[1]
    else:
        r += repr_node(node[1])
    r += ")"
    return r

node_p_()
""" =>
(AAA,BBB)
((AAA,BBB),CCC)
(((AAA,BBB),CCC),DDD)
(EEE,FFF)
((((AAA,BBB),CCC),DDD),(EEE,FFF))
"""

Comments

[contact2093]

回答ありがとうございます。
こういう問題を言葉になおしてくださって，助かりました。
今後の勉強の参考にさせていただきます。

Answer 3

内側から順に マッチ ⇒ 置換 することで実現できました。
かなり野暮ったい方法なのであまり達成感が無いですが...

import collections
import itertools
import re


src = r'((((AAA,BBB),CCC),DDD), (EEE,FFF))'

dst = []
work_dir = collections.OrderedDict()

for i in itertools.count():
    m = re.search(r'([^()]+)', src)
    if not m:
        break
        
    s = m.group()
    
    dst.append(s)
    work_dir[f'${i}'] = s
    src = src.replace(s, f'${i}')

for k, v in reversed(work_dir.items()):
    dst = [
        e.replace(k, v) for e in dst
    ]
    
print(*dst, sep='\n')

実行結果 Wandbox

(AAA,BBB)
((AAA,BBB),CCC)
(((AAA,BBB),CCC),DDD)
(EEE,FFF)
((((AAA,BBB),CCC),DDD), (EEE,FFF))

追記： 邪道

思い付いたので書きました。真似はしない方が良いです。

import ast
import re


src = r'((((AAA,BBB),CCC),DDD), (EEE,FFF))'
src = re.sub(r'(\w+)', r'"\1"', src)

work = [ast.literal_eval(src)]
dst = []

while work:
    tmp = work.pop()
    dst.append(tmp)
    
    work += [e for e in tmp if isinstance(e, tuple)]
    

dst = [
    str(e).replace('"', '').replace("'", "")
    for e in reversed(dst)
]
print(*dst, sep='\n')

実行結果 Wandbox

(AAA, BBB)
((AAA, BBB), CCC)
(((AAA, BBB), CCC), DDD)
(EEE, FFF)
((((AAA, BBB), CCC), DDD), (EEE, FFF))