pythonで入れ子上になったテキストの階層構造を取り出す

次のようなテキストを階層ごとに取り出したいです。
aa(bb(dd)cc(ee))ff

これを
dict ={
aa:({bb:dd,cc:ee})
ff:None}
のように取り出したいです。

考えたこととしては
文字列を（で分割し、listにした上で（と）の間をnewlist = [n:m]で抽出してゆく
という方法を試しましたが、親と子の対応がうま作れません。

なんと検索すれば良いかもよくわからず、丸投げのような形になってしまい申し訳ありませんが、ご教授いただけませんでしょうか？

行動規範の内容に同意します

回答3件

複雑な構文なら、パーサーライブラリーを利用したほうがよいです。

ライブラリーを使わずに、単語分割部分から書いてみました。
a.py

python3'
1import re
2
3def break_token(line):
4    ans = []
5    token = ""
6    for c in re.sub(" +", " ", line):
7        if c  == "(" or c == ")":
8            if token != "":
9                ans.append(token)
10                token = ""
11            ans.append(c)
12        elif c == " " and token != "":
13            ans.append(token)
14            token = ""            
15        else:
16            if c != " ":
17                token = token + c
18                tokem = ""
19
20    if token != "":
21        ans.append(token)
22    return ans
23
24def parse(tokens):
25    if len(tokens) == 0:
26        return None, []
27
28    ans= {}
29    while len(tokens) > 0:
30        # print("---", tokens)
31
32        k = tokens[0]
33        if k == ")":
34            break
35
36        tokens = tokens[1::]
37        if len(tokens) < 1:
38            ans[k] = None
39            break
40
41        t = tokens[0]
42        if t == "(":
43            v, tokens = parse_val(tokens[1::])
44            ans[k] = v
45            tokens = tokens[1::]
46        elif t == ")":
47            ans[k] = None
48        else:
49            ans[k] = "**ERR**"
50
51    return [ans, tokens]
52
53def parse_val(tokens):
54    if len(tokens) < 1:
55        return [None, []]
56
57    val = tokens[0]
58    if len(tokens) < 2:
59        return [val, []]
60
61    if tokens[1] != "(":
62        return [val, tokens[1::]]
63
64    val, tokens = parse(tokens)
65    return [val, tokens]
66
67
68tests =[
69    "aa(bb(dd)cc(ee))ff(gg)",
70    "aa(bb(dd)cc(ee))ff",
71    "aa(bb(dd)cc(ee))",
72    "aa(bb(dd)cc)",
73    "aa(bb(dd))",
74    "aa(bb)cc(dd)ff",
75    "aa(bb)cc(dd)",
76    "aa(bb)xx",
77    "aa(bb)",
78    "aa",
79    ""
80]
81for line in tests:
82    print(line)
83    data, tokens = parse(break_token(line))
84    print(" ->", data)

実行例：

投稿2020/01/12 08:45

katoy

総合スコア22328

nifch

2020/01/14 04:00

コードに加えて，パーサーライブラリについても教えてくださりありがとうございます．ライブラリの種類がたくさんあるようなので，最適なライブラリを勉強してみます．

行動規範の内容に同意します

ベストアンサー

あまりスマートでは無いですけど、書いてみました。

Python
1import collections
2import re
3
4
5Brace = collections.namedtuple('Brace', ['start', 'end', 'level'])
6
7def find_braces(src):
8    stack = collections.deque()
9    braces = []
10        
11    level = 0
12    for i, ch in enumerate(src):
13        if ch == '(':
14            level += 1
15            stack.append(i)
16        elif ch == ')':
17            level -= 1
18            braces.append(
19                Brace(stack.pop(), i+1, level)
20            )
21            
22    return braces
23
24
25def parse(src):
26    if src == 'None':
27        return None
28    if re.fullmatch(r'[^()]+', src):
29        return src
30    
31    # 
32    if not src.endswith(')'):
33        src += '(None)'
34        
35    outer_braces = [
36        brace for brace in find_braces(src)
37        if brace.level == 0
38    ]
39    
40    dst = {}
41    offset = 0
42    for start, end, _ in outer_braces:
43        key = src[offset:start]
44        val = parse(
45            src[start:end][1:-1]
46        )
47        dst[key] = val
48
49        offset = end
50        
51    return dst
52    
53    
54src = 'aa(bb(dd)cc(ee))ff'
55dst = parse(src)
56
57print(dst)

実行結果 Wandbox

{'aa': {'bb': 'dd', 'cc': 'ee'}, 'ff': None}

投稿2020/01/09 14:59

LouiS0616

総合スコア35676

nifch

2020/01/14 03:54

ご回答下さりありがとうございます．すみません，find_braces関数内のcollectionsライブラリでの処理について教えていただけないでしょうか？ elif ch == ')': level -= 1 braces.append( Brace(stack.pop(), i+1, level) ) 自分でも書いてみたのですが，上記のコードの処理の意味がよくわかりません．

LouiS0616

2020/01/14 04:26

開き括弧と閉じ括弧の対応を取るために、スタックを利用しています。文字列を先頭から一文字ずつ読んでいき、( を見つけたらその位置をスタックに押し込みます。 ) を見つけたらスタックから ( の位置を取り出します。 bracesは対応する括弧をまとめたリストで、各要素はBrace型です。 Braceは名前付きタプルで、(開き括弧の位置, 閉じ括弧の位置+1, 深さ) の組になっています。 levelは入れ子の深さです。

nifch

2020/01/15 05:52

丁寧なご解説、ありがとうございます。理解できました！

行動規範の内容に同意します

こんにちは

aa(bb(dd)cc(ee))ff という文字列から、

json
1{ "aa":{ "bb":"dd", "cc":"ee" }, "ff":null }

というJSON形式の文字列を作り、これをパースするという方法はいかがでしょう？
以下は、その一例です。

python3
1import re
2import json
3
4
5def to_json_str(text):
6    text = re.compile(r'([a-z]+)$').sub('\1()', text)
7    text = text.replace('(', ':{')
8    text = text.replace(')', '},')
9    text = re.compile(r'{\s*([a-z]+)\s*}').sub('"\1"', text)
10    text = text.strip(',')
11    text = re.sub(r',\s*}', '}', text)
12    text = re.sub(r'{\s*}', 'null', text)
13    text = re.compile(r'([a-z]+):').sub('"\1":', text)
14
15    return '{%s}' % text
16
17
18json_str = to_json_str('aa(bb(dd)cc(ee))ff') # => {"aa":{"bb":"dd","cc":"ee"},"ff":null}
19
20dic = json.loads(json_str)
21
22print(dic)    # => {'bb': 'dd', 'cc': 'ee'}, 'ff': None}
23

動作確認用Repl.it: https://repl.it/@jun68ykt/Q234191

関数 to_json_str の本体は修正あるいはリファクタの余地があるかもしれませんが、JSONを経由するという考え方を提示することがこの回答の主旨になります。

参考になれば幸いです。

補足

以下、参考までに補足します。

なんと検索すれば良いかもよくわからず、

とのことですが、 aa(bb(dd)cc(ee))ff のような、開くカッコと閉じるカッコがきちんと対応して出現するという規則に沿った文字列のパーサーを（私の回答コードのような既存モジュールの力を借りずに）自作するということになると、理屈としては

文脈自由文法
プッシュダウンオートマトン

といった概念が（根本的なところでは）関わってくるものと思います。従って、何らかの文脈自由文法によって生成される文字列をパースするというテーマで検索すれば、参考になるコードがみつかるかもしれません。

投稿2020/01/09 13:56

編集2020/01/09 15:04

jun68ykt

総合スコア9058

nifch

2020/01/14 03:44 編集

ありがとうございます．JSON経由はコードも可読性がよく，汎用性も良さそうですね． reライブラリをまだまだ使いこなせていないので，大変参考になります．教えていただいた文脈自由文法とプッシュダウンオートマトンについて調べてみた所，全く理解できなかったためしっかり勉強してみようと思います．糸口まで丁寧に教えてくださりありがとうございます．

jun68ykt

2020/01/15 23:18

どういたしまして。オートマトンについて、一度しっかり勉強されるということでしたら、まとまった書籍を一冊お読みになるとよいかもしれません。私は下記の本で学びました。計算理論の基礎 [原著第2版] 1.オートマトンと言語 https://www.amazon.co.jp/dp/4320122070/ 全３冊で完結するシリーズの１冊目で、この本自体は、薄くて取り組みやすいです。目次をみるとわかりますが、文脈自由文法の前に、有限オートマトンについて書かれており、その中で、正規表現とオートマトンの等価性について学べます。練習問題がたくさん載ってますが、ご質問にあるような開くカッコと閉じるカッコが、きちんと対応して出現する文字列を、正規表現では表せないことを証明する練習問題が、どこかに載っていた記憶があります。

行動規範の内容に同意します

あなたの回答