入れ子のカッコの切り出し

2021/MAR/22

文字列中のカッコの部分をリストでまとめる処理について。

まずは単純な仕様から

'foo ( bar ) hoge'

の文字列を

[ 'foo ', [ ' bar ' ], ' hoge' ]

というリストに切り分ける処理を考えてみます。

とりあえず

• '('よりも前の部分の文字列
• '('から')'までの内部の文字列が要素になってるリスト
• ')'よりも前の部分の文字列

の3つの要素をリストにして返す事にしてみます。

処理をぼんやり考えてみる

def split_br( s ):
	...

な関数に文字列を与えると、要素3のリストが返ることに。

まずはsの中に'('を探すでしょう。

そして、'('までの文字列と、')'より後ろの文字列に分割するでしょう。

さて、ここで「!」

文字列s中に'('が無ければ?

明らかにカッコのバランスが崩れてるということで、 意図した処理から外れてしまいます。

この場合、とりあえずリストの「てい」にして返す必要も無いので、 入力した文字列sをそのまま返す仕様にしてみようかと。

ならば「!」

文字列s中に’)'が無くても、同様にカッコのバランスが崩れているはずで、 意図した切り出し動作結果のリストの「てい」にする必要もなく。

この場合も、文字列sをそのまま返すことに。

さらに'('と')'両方あったとしても、

'xxx ) yyy ( zzz'

の順番なら、やっぱりダメ扱いにしないと、です。 この場合も文字列sを、そのまま返すことにしてみます。

コードにしてみます

仕様を満たす処理をコードにまとめてみると

#!/usr/bin/env python

get_idx = lambda s, c, dv=-1: s.index( c ) if c in s else dv

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

	h = s[ : i ]
	m = s[ i + 1 : j ]
	t = s[ j + 1 : ]
	return [ h, [ m ], t ]

get_idx( s, c, dv=-1 )

は、文字列s中のcのindexを返します。

ただし、s中にcがなければ値dvを返します。

if i < 0 or j < 0 or j < i:
	return s

'('か')'が無い場合、両方あっても')', '('の順番で現れる場合は、 入力文字列sをそのまま返します。

動作確認

まずは、意図した動作の確認から

>>> import foo

>>> foo.split_br( 'foo ( bar ) hoge' )
['foo ', [' bar '], ' hoge']

つづいて意図してない文字列の場合

>>> foo.split_br( 'foo bar hoge' )
'foo bar hoge'

>>> foo.split_br( 'foo ( bar hoge' )
'foo ( bar hoge'

>>> foo.split_br( 'foo bar ) hoge' )
'foo bar ) hoge'

>>> foo.split_br( 'foo ) bar ( hoge' )
'foo ) bar ( hoge'

確かに入力した文字列が返ります。

後方に複数ある場合の対応

'foo ( bar ) hoge)'

だけじゃなくて

'foo ( bar ) hoge ( fuga ) guha ( abc ) def'

のように複数の場合に対応してみます。

結果は

[ 'foo ', [ ' bar ' ], ' hoge ', [ ' fuga ' ], ' guha ', [ ' abc ' ], ' def' ]

このようなリストで。

「ループ」の処理で考えても良いですが、ここはひとつ「再帰」で考えてみます。

自分の中で再帰の処理をかく時のコツは、 まずは完成結果のイメージをしっかり描くこと。

複数対応してない既存の処理中から、 「完成した後」の動作をするものと強く思いこんで、 自身の関数を再帰で呼び出すという覚悟で。

既存の処理の後半部分

h = s[ : i ]
m = s[ i + 1 : j ]
t = s[ j + 1 : ]
return [ h, [ m ], t ]

このtの部分に、残りの未処理のカッコが残ってるはず。

なので split_br( t ) を呼び出せば、 残っているカッコが全てうまく処理されて返されるものと強くイメージして

h = s[ : i ]
m = s[ i + 1 : j ]
t = s[ j + 1 : ]

r = split_br( t )

そして、tにカッコが含まれてなかったり、カッコのバランスが崩れていたりしたら、 rは文字列tがそのまま返ってくるはずです。

そのときは、複数じゃないときの結果と同じ

return [ h, [ m ], t ]

なので

return [ h, [ m ], r ]

を返せばよいはず。

tに意図したカッコの記述があると、rはリストが返るはずです。

さらに、tに複数のカッコの記述があったとしても、 ちゃんと完成されたリストで返ってくるはずと、強くイメージ。

となると、返すべき結果は、rのリストの先頭に、h と [ m ] を挿入したリスト。

リストの結合で考えると

[ h, [ m ] ] + r

後半をまとめると

r = split_br( t )
if r == t:
	return [ h, [ m ], t ]

return [ h, [ m ] ] + r

まぁ、処理を共通化して

r = split_br( t )
if r == t:
	r = [ r ]
return [ h, [ m ] ] + r

コード

#!/usr/bin/env python

get_idx = lambda s, c, dv=-1: s.index( c ) if c in s else dv

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

	h = s[ : i ]
	m = s[ i + 1 : j ]
	t = s[ j + 1 : ]

	r = split_br( t )
	if r == t:
		r = [ r ]
	return [ h, [ m ] ] + r

動作確認

複数のカッコ

>>> import foo2

>>> foo2.split_br( 'foo ( bar ) hoge ( fuga ) guha ( abc ) def' )
['foo ', [' bar '], ' hoge ', [' fuga '], ' guha ', [' abc '], ' def']

1組だけのカッコでも問題ないか

>>> foo2.split_br( 'foo ( bar ) hoge' )
['foo ', [' bar '], ' hoge']

>>> foo2.split_br( 'foo bar hoge' )
'foo bar hoge'

>>> foo2.split_br( 'foo ( bar hoge' )
'foo ( bar hoge'

>>> foo2.split_br( 'foo bar ) hoge' )
'foo bar ) hoge'

>>> foo2.split_br( 'foo ) bar ( hoge' )
'foo ) bar ( hoge'

従来通りの動作です。

入れ子対応

カッコが入れ子になってネストしてる場合の対応を考えてみます。

'foo ( bar ( hoge ) fuga ) guha ( abc ) def'

ならば

[ 'foo ', [ ' bar ', [ ' hoge ' ], ' fuga ' ], ' guha ', [ ' abc ' ], ' def' ]

に。

'foo ( bar ( hoge ) fuga ( guha ) abc ) def'

ならば

[ 'foo ', [ ' bar ', [ ' hoge ' ], ' fuga ', [ ' guha ' ], ' abc ' ], ' def' ]

に。

これこそ「再帰」。

h = s[ : i ]
m = s[ i + 1 : j ]
t = s[ j + 1 : ]

で切り出した m の部分に、さらにカッコの記述がある場合です。

ですが、入れ子の仕様を受け入れたとたんに、これまで前提が崩れます。

既存のコードの前半部分

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

	h = s[ : i ]
	m = s[ i + 1 : j ]
	t = s[ j + 1 : ]

最初に見つける')'が、'('にバランスして対応したものになるとは限りません。

ですが、ここでも「再帰のこつ」。

一旦split_br(s)が既に入れ子に対応が終わっていると、強くイメージします。

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

ここまでは、入れ子だろうが、最低限閉じるカッコが必要という条件は 変わらないはずなので、このままで矛盾は無いはずです。

そして

h = s[ : i ]

ここも問題なし。

jがトップレベルの閉じカッコを指しているとは限らないので、 以降のjの使用箇所が問題です。

そこで再帰。

t = s[ i + 1 : ]
r = split_br( t )

として、開きカッコよりも後ろを全部切り出して、 とりあえず完成してる想定で再帰呼び出し。

t の中に入れ子のカッコの記述があれば、 それなりに完成したリストが返ってきつつ、 リストの最後の要素の文字列に、 バランスしてない余った閉じカッコが含まれているはず。

いや、記述が不完全であれば、閉じカッコが含まれていない可能性もあります。

t の中に入れ子のカッコが記述がなくて、以前の想定の範囲であれば、 文字列が返ってくるはず。

これも、閉じカッコが含まれている場合もあれば、含まれていない場合もあると。

ここは、複数対応のときの再帰と同様に、 再帰呼び出しの結果が文字列ならば、一旦リストに仕立てるのが吉でしょうか。

リストの最後の要素の文字列について、閉じカッコの処理につなげてみます。

t = s[ i + 1 : ]
r = split_br( t )
if r == t:
	r = [ r ]
t = r[ -1 ]

そして、この後続の文字列tにトップレベルの閉じカッコが無ければ、 カッコのバランスが取れてないはずなので、 全部おじゃんで文字列sを返します。

もし、後続の文字列tに閉じカッコより先に開きカッコがきていたら?

さらなる処理が必要?

いえ、split_br()がすでに入れ子対応完璧とイメージしていれば、大丈夫。

そのような状態の文字列が、帰り値文字列や、リストの末尾文字列に残っていたとしたら、 それは、有効な記述ではなく、バランスせずに残されていた場合になるはずです。

なので、先に開きカッコがきてる場合も、トップレベルの閉じカッコとバランスせずで、 全部おじゃん扱いになります。

t = s[ i + 1 : ]
r = split_br( t )
if r == t:
	r = [ r ]
t = r[ -1 ]
i = get_idx( t, '(' )
j = get_idx( t, ')' )

if j < 0 or ( i >= 0 and i < j ):
	return s

後続文字列tから、閉じカッコ以前と以降に分離して、 以前の方をカッコの中のリストの末尾にさしもどし。

以降の方は、これまでの処理の後続文字列として扱えばよろしかろう。

よって既存の複数対応箇所

t = s[ j + 1 : ]

r = split_br( t )
if r == t:
	r = [ r ]
return [ h, [ m ] ] + r

の部分が

( r[ -1 ], t ) = ( t[ : j ], t[ j + 1 : ] )
m = r

r = split_br( t )
if r == t:
	r = [ r ]
return [ h, m ] + r

このように。

mは以前は文字列でしたが、今回はリストなので、このように。

コード

#!/usr/bin/env python

get_idx = lambda s, c, dv=-1: s.index( c ) if c in s else dv

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

	h = s[ : i ]

	t = s[ i + 1 : ]
	r = split_br( t )
	if r == t:
		r = [ r ]
	t = r[ -1 ]
	i = get_idx( t, '(' )
	j = get_idx( t, ')' )

	if j < 0 or ( i >= 0 and i < j ):
		return s

	( r[ -1 ], t ) = ( t[ : j ], t[ j + 1 : ] )
	m = r

	r = split_br( t )
	if r == t:
		r = [ r ]
	return [ h, m ] + r

動作確認

入れ子のカッコ

>>> import foo3

>>> foo3.split_br( 'foo ( bar ( hoge ) fuga ) guha ( abc ) def' )
['foo ', [' bar ', [' hoge '], ' fuga '], ' guha ', [' abc '], ' def']

>>> foo3.split_br( 'foo ( bar ( hoge ) fuga ( guha ) abc ) def' )
['foo ', [' bar ', [' hoge '], ' fuga ', [' guha '], ' abc '], ' def']

従来の動作確認分

>>> foo3.split_br( 'foo ( bar ) hoge ( fuga ) guha ( abc ) def' )
['foo ', [' bar '], ' hoge ', [' fuga '], ' guha ', [' abc '], ' def']

>>> foo3.split_br( 'foo ( bar ) hoge' )
['foo ', [' bar '], ' hoge']

>>> foo3.split_br( 'foo bar hoge' )
'foo bar hoge'

>>> foo3.split_br( 'foo ( bar hoge' )
'foo ( bar hoge'

>>> foo3.split_br( 'foo bar ) hoge' )
'foo bar ) hoge'

>>> foo3.split_br( 'foo ) bar ( hoge' )
'foo ) bar ( hoge'

空白の扱い

ここまで単語の前後に必ず空白ありで試してました。

コード中で空白文字を特別に意識して扱ってる部分はなく、 結果の文字列に空白は含まれています。

>>> foo3.split_br( 'foo ( bar ( hoge ) fuga ) guha ( abc ) def' )
['foo ', [' bar ', [' hoge '], ' fuga '], ' guha ', [' abc '], ' def']

入力文字列から空白文字を削除してみると

>>> foo3.split_br( 'foo(bar(hoge)fuga)guha(abc)def' )
['foo', ['bar', ['hoge'], 'fuga'], 'guha', ['abc'], 'def']

まぁそうなりますね。

では、ある単語が空白文字ならば?

たとえばbarが空白文字なら

>>> foo3.split_br( 'foo( (hoge)fuga)guha(abc)def' )
['foo', [' ', ['hoge'], 'fuga'], 'guha', ['abc'], 'def']

例えばhogeも空白文字ならば?

>>> foo3.split_br( 'foo( ( )fuga)guha(abc)def' )
['foo', [' ', [' '], 'fuga'], 'guha', ['abc'], 'def']

ではこの空白文字を削除したら?

>>> foo3.split_br( 'foo(()fuga)guha(abc)def' )
['foo', ['', [''], 'fuga'], 'guha', ['abc'], 'def']

split_br()がカッコを含む記述を処理して返すリストは、かたくなに

先頭要素は文字列
次の要素はカッコの中身でリスト
次の要素は文字列
次の要素はカッコの中身でリスト
	:
最後の要素は文字列

の形式が守られています。

>>> foo3.split_br( '()' )
['', [''], '']

さすがに空白文字でもない「から文字」のときは、削除して良いのでは?

foo3.pyではreturnは3箇所。

うち2箇所は入力文字列sをそのまま返すので、ここは無関係。

最後の

return [ h, m ] + r

mもrも再帰呼び出しの結果なので、「から文字」対策ができていると、 強くイメージすれば、問題はhだけだという事が見えてきます。

hは前半で入力文字列から切り出して、ずっと手付かずでここまできます。

なので、hが「から文字」のときは return [ m ] + r にすれば良さげです。

if not h:
	return [ m ] + r
return [ h, m ] + r

でも良いですが、return箇所を1つに絞るのであれば

h = [ h ] if h else []
return h + [ m ] + r

くらいでしょうか。

どうせなら、最初に切り出したときに対策しておくべきかと。

h = s[ : i ]

で

h = s[ : i ]
h = [ h ] if h else []

しておいて、最後に

return h + [ m ] + r

これで返す。

なんか、もやもや。

「!」

閉じカッコも切り出しをしてるので、そちらも対策必要では?

>mもrも再帰呼び出しの結果なので、「から文字」対策ができていると、
>強くイメージすれば、問題はhだけだという事が見えてきます。

の前言撤回です。

split_br()呼び出しから返ってきた値から、 さらに閉じカッコの切り出しをしてるので、対策が必要でした。

( r[ -1 ], t ) = ( t[ : j ], t[ j + 1 : ] )
m = r

ここで j が閉じカッコの位置。

t[ : j ] 結果が「から文字列」ならば、それが格納される r[ -1 ]　は、 リストrの末尾要素の削除で対応かと。

( t2, t ) = ( t[ : j ], t[ j + 1 : ] )
t2 = [ t2 ] if t2 else []
m = r[ : -1 ] + t2

そして関数の最後の部分の処理

r = split_br( t )
if r == t:
	r = [ r ]

return h + [ m ] + r

ここで後続の文字列tが「から文字」ならば、 split_br( '' ) の返り値は、開きカッコも閉じカッコもなく入力文字列のままで、から文字が返ります。

r が [ '' ] になって、返るリストの末尾の要素が「から文字」に。

なので、

r = split_br( t )
if r == t:
	r = [ r ] if r else []

return h + [ m ] + r

でよろしいかと。

コード

#!/usr/bin/env python

get_idx = lambda s, c, dv=-1: s.index( c ) if c in s else dv

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

	h = s[ : i ]
	h = [ h ] if h else []

	t = s[ i + 1 : ]
	r = split_br( t )
	if r == t:
		r = [ r ]
	t = r[ -1 ]
	i = get_idx( t, '(' )
	j = get_idx( t, ')' )

	if j < 0 or ( i >= 0 and i < j ):
		return s

	( t2, t ) = ( t[ : j ], t[ j + 1 : ] )
	t2 = [ t2 ] if t2 else []
	m = r[ : -1 ] + t2

	r = split_br( t )
	if r == t:
		r = [ r ] if r else []

	return h + [ m ] + r

動作確認

>>> import foo4

>>> foo4.split_br( 'foo(()fuga)guha(abc)def' )
['foo', [[], 'fuga'], 'guha', ['abc'], 'def']

>>> foo4.split_br( 'foo(bar(hoge)fuga)guha(abc)def' )
['foo', ['bar', ['hoge'], 'fuga'], 'guha', ['abc'], 'def']

>>> foo4.split_br( 'foo( (hoge)fuga)guha(abc)def' )
['foo', [' ', ['hoge'], 'fuga'], 'guha', ['abc'], 'def']

>>> foo4.split_br( 'foo( ( )fuga)guha(abc)def' )
['foo', [' ', [' '], 'fuga'], 'guha', ['abc'], 'def']

>>> foo4.split_br( 'foo(()fuga)guha(abc)def' )
['foo', [[], 'fuga'], 'guha', ['abc'], 'def']

>>> foo4.split_br( '()' )
[[]]

>>> foo4.split_br( 'foo ( bar ( hoge ) fuga ) guha ( abc ) def' )
['foo ', [' bar ', [' hoge '], ' fuga '], ' guha ', [' abc '], ' def']

>>> foo4.split_br( 'foo ( bar ( hoge ) fuga ( guha ) abc ) def' )
['foo ', [' bar ', [' hoge '], ' fuga ', [' guha '], ' abc '], ' def']

>>> foo4.split_br( 'foo ( bar ) hoge ( fuga ) guha ( abc ) def' )
['foo ', [' bar '], ' hoge ', [' fuga '], ' guha ', [' abc '], ' def']

>>> foo4.split_br( 'foo ( bar ) hoge' )
['foo ', [' bar '], ' hoge']

>>> foo4.split_br( 'foo bar hoge' )
'foo bar hoge'

>>> foo4.split_br( 'foo ( bar hoge' )
'foo ( bar hoge'

>>> foo4.split_br( 'foo bar ) hoge' )
'foo bar ) hoge'

>>> foo4.split_br( 'foo ) bar ( hoge' )
'foo ) bar ( hoge'

元も文字列への復帰処理

空白文字を特別扱いして、削除しておりませんので、完全に元に戻せるはずですね。

リストのある要素が、リストならばそれはカッコの中の情報なので、前後に 開きカッコ、閉じカッコを追加すればよさげです。

ただし、一番外側のリストは、分解した結果としてのリストなので、カッコの中身として扱ってはダメ。

素直にかくと

def join_br( lst ):
	def cv( e ):
		if type( e ) == list:
			return '(' + ''.join( map( cv, e ) ) + ')'
		return e

	return ''.join( map( cv, lst ) )

join, map のくだりが同じなので

def join_br( lst ):
	def cv( e, add_br=True ):
		if type( e ) == list:
			s = ''.join( map( cv, e ) )
			if add_br:
				s = '(' + s + ')'
			return s
		return e

	return cv( lst, False )

なんか、かえって行数が増えて複雑に見えるかも。

コード

#!/usr/bin/env python

get_idx = lambda s, c, dv=-1: s.index( c ) if c in s else dv

def split_br( s ):
	i = get_idx( s, '(' )
	j = get_idx( s, ')' )

	if i < 0 or j < 0 or j < i:
		return s

	h = s[ : i ]
	h = [ h ] if h else []

	t = s[ i + 1 : ]
	r = split_br( t )
	if r == t:
		r = [ r ]
	t = r[ -1 ]
	i = get_idx( t, '(' )
	j = get_idx( t, ')' )

	if j < 0 or ( i >= 0 and i < j ):
		return s

	( t2, t ) = ( t[ : j ], t[ j + 1 : ] )
	t2 = [ t2 ] if t2 else []
	m = r[ : -1 ] + t2

	r = split_br( t )
	if r == t:
		r = [ r ] if r else []

	return h + [ m ] + r

def join_br( lst ):
	def cv( e, add_br=True ):
		if type( e ) == list:
			s = ''.join( map( cv, e ) )
			if add_br:
				s = '(' + s + ')'
			return s
		return e

	return cv( lst, False )

動作確認

>>> import foo5

>>> lst = foo5.split_br( 'foo ( bar ( hoge ) fuga ) guha ( abc ) def' )
>>> lst
['foo ', [' bar ', [' hoge '], ' fuga '], ' guha ', [' abc '], ' def']

>>> foo5.join_br( lst )
'foo ( bar ( hoge ) fuga ) guha ( abc ) def'

>>> foo5.split_br( 'foo(bar(hoge)fuga)guha(abc)def' )
['foo', ['bar', ['hoge'], 'fuga'], 'guha', ['abc'], 'def']
>>> foo5.join_br( foo5.split_br( 'foo(bar(hoge)fuga)guha(abc)def' ) )
'foo(bar(hoge)fuga)guha(abc)def'

>>> foo5.split_br( 'foo( ( )fuga)guha(abc)def' )
['foo', [' ', [' '], 'fuga'], 'guha', ['abc'], 'def']
>>> foo5.join_br( foo5.split_br( 'foo( ( )fuga)guha(abc)def' ) )
'foo( ( )fuga)guha(abc)def'

>>> foo5.split_br( '()' )
[[]]
>>> foo5.join_br( foo5.split_br( '()' ) )
'()'