# Constants for making it easy
leftBrackets = [ '(' , '{' , '[' ] ;
rightBrackets = [ ')' , '}' , ']' ] ;
examples = [ '((your[drink {remember to}]) ovaltine)' ,
'[racket for {brackets (matching) is a} computers]' ,
'[can {and it(it (mix) up ) } look silly]' ,
'((your[drink {remember to))) ovaltine)' ,
'[can {and it(it (mix) up ) look silly]' ,
'[racket for brackets (matching) is a} computers]' ,
'{years [four score] ago (and seven) our fathers}'
] ;
def testForErrors( example) :
for leftBracket, rightBracket in zip ( leftBrackets, rightBrackets) :
if ( example.count ( leftBracket) != example.count ( rightBracket) ) :
print 'Generates an error "Missing opening bracket' ;
return False ;
return True ;
def MARCHMADNESS( s) :
if s == '' :
return '' ;
for leftBracket, rightBracket in zip ( leftBrackets, rightBrackets) :
s = s.replace ( leftBracket, '(' ) ;
s = s.replace ( rightBracket, ')' ) ;
leftBracketIndex = s.rfind ( '(' ) ;
rightBracketIndex = s.find ( ')' ) ;
while ( leftBracketIndex > rightBracketIndex) :
leftBracketIndex = s.rfind ( '(' , 0 , leftBracketIndex) ;
return s[ leftBracketIndex+1 :rightBracketIndex] + ' ' + str ( MARCHMADNESS( s[ 0 :leftBracketIndex] + s[ rightBracketIndex+1 :] ) ) .strip ( ) .replace ( ' ' , ' ' ) ;
for example in examples:
if ( testForErrors( example) == False ) :
continue ;
print MARCHMADNESS( example) ;
IyBDb25zdGFudHMgZm9yIG1ha2luZyBpdCBlYXN5CmxlZnRCcmFja2V0cyA9IFsnKCcsICd7JywgJ1snIF07CnJpZ2h0QnJhY2tldHMgPSBbJyknLCAnfScsICddJ107CmV4YW1wbGVzID0gWyAgJygoeW91cltkcmluayB7cmVtZW1iZXIgdG99XSkgb3ZhbHRpbmUpJywKICAgICAgICAgICAgICAnW3JhY2tldCBmb3Ige2JyYWNrZXRzIChtYXRjaGluZykgaXMgYX0gY29tcHV0ZXJzXScsCiAgICAgICAgICAgICAgJ1tjYW4ge2FuZCBpdChpdCAobWl4KSB1cCApIH0gbG9vayBzaWxseV0nLAogICAgICAgICAgICAgICcoKHlvdXJbZHJpbmsge3JlbWVtYmVyIHRvKSkpIG92YWx0aW5lKScsCiAgICAgICAgICAgICAgJ1tjYW4ge2FuZCBpdChpdCAobWl4KSB1cCApIGxvb2sgc2lsbHldJywKICAgICAgICAgICAgICAnW3JhY2tldCBmb3IgYnJhY2tldHMgKG1hdGNoaW5nKSBpcyBhfSBjb21wdXRlcnNdJywKICAgICAgICAgICAgICAne3llYXJzIFtmb3VyIHNjb3JlXSBhZ28gKGFuZCBzZXZlbikgb3VyIGZhdGhlcnN9JwogICAgICAgICAgXTsKCmRlZiB0ZXN0Rm9yRXJyb3JzKGV4YW1wbGUpOgogIGZvciBsZWZ0QnJhY2tldCwgcmlnaHRCcmFja2V0IGluIHppcChsZWZ0QnJhY2tldHMsIHJpZ2h0QnJhY2tldHMpOgogICAgaWYoZXhhbXBsZS5jb3VudChsZWZ0QnJhY2tldCkgIT0gZXhhbXBsZS5jb3VudChyaWdodEJyYWNrZXQpKToKICAgICAgcHJpbnQgJ0dlbmVyYXRlcyBhbiBlcnJvciAiTWlzc2luZyBvcGVuaW5nIGJyYWNrZXQnOwogICAgICByZXR1cm4gRmFsc2U7CgogIHJldHVybiBUcnVlOwoKZGVmIE1BUkNITUFETkVTUyhzKToKICBpZiBzID09ICcnOgogICAgcmV0dXJuICcnOwoKICBmb3IgbGVmdEJyYWNrZXQsIHJpZ2h0QnJhY2tldCBpbiB6aXAobGVmdEJyYWNrZXRzLCByaWdodEJyYWNrZXRzKToKICAgIHMgPSBzLnJlcGxhY2UobGVmdEJyYWNrZXQsICcoJyk7CiAgICBzID0gcy5yZXBsYWNlKHJpZ2h0QnJhY2tldCwgJyknKTsKCiAgbGVmdEJyYWNrZXRJbmRleCA9IHMucmZpbmQoJygnKTsKICByaWdodEJyYWNrZXRJbmRleCA9IHMuZmluZCgnKScpOwogIHdoaWxlKGxlZnRCcmFja2V0SW5kZXggPiByaWdodEJyYWNrZXRJbmRleCk6CiAgICBsZWZ0QnJhY2tldEluZGV4ID0gcy5yZmluZCgnKCcsIDAsIGxlZnRCcmFja2V0SW5kZXgpOwoKICByZXR1cm4gc1tsZWZ0QnJhY2tldEluZGV4KzE6cmlnaHRCcmFja2V0SW5kZXhdKyAnICcgKyBzdHIoTUFSQ0hNQURORVNTKHNbMDpsZWZ0QnJhY2tldEluZGV4XSArIHNbcmlnaHRCcmFja2V0SW5kZXgrMTpdKSkuc3RyaXAoKS5yZXBsYWNlKCcgICcsICcgJyk7Cgpmb3IgZXhhbXBsZSBpbiBleGFtcGxlczoKICBpZih0ZXN0Rm9yRXJyb3JzKGV4YW1wbGUpID09IEZhbHNlKToKICAgIGNvbnRpbnVlOwogIHByaW50IE1BUkNITUFETkVTUyhleGFtcGxlKTsKCg==