正規表現パズル

行頭直後の開き括弧から、対応する閉じ括弧まで中身を含めて検索する。
括弧のネストは許可する。

擬似括弧として開き括弧をS、閉じ括弧をEとする。

検索前


検索後

対象データ

S 1+2+3 E
S 1+2+S 3+4 E*5 E+1+2
S 1+2+S 3+4 E*5 E+S 1+2 E*3
S S S 1+2 E *2 E*3 E+ S1+2 E
1+2+S 1*5 E
S S E S E E
S S S E E S E E

正規表現

^S[^SE]*(?<rec>S[^SE]*\g<rec>[^SE]*E[^SE]*\g<rec>|)[^SE]*E

別解1

^S[^SE]*(?<rec>S[^SE]*\g<rec>E[^SE]*\g<rec>|)[^SE]*E

別解2

^S[^SE]*(?<rec>S[^SE]*\g<rec>E[^SE]*\g<rec>|)E

別解3

^S(?<rec>([^SE]|S\g<rec>E)*)E

別解4

^(?<rec>S([^SE]|\g<rec>)*E)

解説

再帰であっても、
SおよびEの直後に0以上の量指定子があればいいと考えて
別解1,別解2と変形してます。

詳説正規表現3版の472ページからPHPの鬼車でのサンプルがあります。

#Rubyでのソースと実行結果

wStr = '^S[^SE]*(?<rec>S[^SE]*\g<rec>E[^SE]*\g<rec>|)E'
ConstRegex = Regexp.new(wStr)
hairetu = Array.new
hairetu.push('S 1+2+3 E')
hairetu.push('S 1+2+S 3+4 E*5 E+1+2')
hairetu.push('S 1+2+S 3+4 E*5 E+S 1+2 E*3')
hairetu.push('S S S 1+2 E *2 E*3 E+ S1+2 E')
hairetu.push('1+2+S 1*5 E')
hairetu.push('S S E S E E')
hairetu.push('S S S E E S E E')

puts "Pattern #{ConstRegex.source}"
for i in (0..hairetu.length-1)
    willOut = sprintf("Line%02d",i+1) + " #{hairetu[i]} "
    work = ConstRegex.match(hairetu[i]).to_a[0]
    if work then
        willOut += 'matchs ' + work
    else
        willOut += 'no match'
    end
    puts willOut
end

#実行結果
Pattern ^S[^SE]*(?<rec>S[^SE]*\g<rec>E[^SE]*\g<rec>|)E
Line01 S 1+2+3 E matchs S 1+2+3 E
Line02 S 1+2+S 3+4 E*5 E+1+2 matchs S 1+2+S 3+4 E*5 E
Line03 S 1+2+S 3+4 E*5 E+S 1+2 E*3 matchs S 1+2+S 3+4 E*5 E
Line04 S S S 1+2 E *2 E*3 E+ S1+2 E matchs S S S 1+2 E *2 E*3 E
Line05 1+2+S 1*5 E no match
Line06 S S E S E E matchs S S E S E E
Line07 S S S E E S E E matchs S S S E E S E E