/*
* Java Program to Check for balanced paranthesis by using Stacks
*/
import java.util.* ;
public class ParenthesisMatching
{
public static void main
( String [ ] args
) {
Scanner scan
= new Scanner
( System .
in ) ; /* Creating Stack */
Stack< Integer> stk = new Stack< Integer> ( ) ;
System .
out .
println ( "Parenthesis Matching Test\n " ) ; /* Accepting expression */
System .
out .
println ( "Enter expression" ) ; int len = exp.length ( ) ;
System .
out .
println ( "\n Matches and Mismatches:\n " ) ; for ( int i = 0 ; i < len; i++ )
{
char ch = exp.charAt ( i) ;
if ( ch == '(' )
stk.push ( i) ;
else if ( ch == ')' )
{
try
{
int p = stk.pop ( ) + 1 ;
System .
out .
println ( "')' at index " + ( i
+ 1 ) + " matched with ')' at index " + p
) ; }
{
System .
out .
println ( "')' at index " + ( i
+ 1 ) + " is unmatched" ) ; }
}
}
while ( ! stk.isEmpty ( ) )
System .
out .
println ( "'(' at index " + ( stk.
pop ( ) + 1 ) + " is unmatched" ) ; }
}
LyoKICogIEphdmEgUHJvZ3JhbSB0byBDaGVjayBmb3IgYmFsYW5jZWQgcGFyYW50aGVzaXMgYnkgdXNpbmcgU3RhY2tzCiAqLwogCmltcG9ydCBqYXZhLnV0aWwuKjsKIApwdWJsaWMgY2xhc3MgUGFyZW50aGVzaXNNYXRjaGluZwp7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSAKICAgIHsKICAgICAgICBTY2FubmVyIHNjYW4gPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwogICAgICAgIC8qIENyZWF0aW5nIFN0YWNrICovCiAgICAgICAgU3RhY2s8SW50ZWdlcj4gc3RrID0gbmV3IFN0YWNrPEludGVnZXI+KCk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJQYXJlbnRoZXNpcyBNYXRjaGluZyBUZXN0XG4iKTsKICAgICAgICAvKiBBY2NlcHRpbmcgZXhwcmVzc2lvbiAqLwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiRW50ZXIgZXhwcmVzc2lvbiIpOwogICAgICAgIFN0cmluZyBleHAgPSBzY2FuLm5leHQoKTsgICAgICAgIAogICAgICAgIGludCBsZW4gPSBleHAubGVuZ3RoKCk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJcbk1hdGNoZXMgYW5kIE1pc21hdGNoZXM6XG4iKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbjsgaSsrKQogICAgICAgIHsgICAgCiAgICAgICAgICAgIGNoYXIgY2ggPSBleHAuY2hhckF0KGkpOwogICAgICAgICAgICBpZiAoY2ggPT0gJygnKQogICAgICAgICAgICAgICAgc3RrLnB1c2goaSk7CiAgICAgICAgICAgIGVsc2UgaWYgKGNoID09ICcpJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdHJ5CiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IHAgPSBzdGsucG9wKCkgKyAxOwogICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiJyknIGF0IGluZGV4ICIrKGkrMSkrIiBtYXRjaGVkIHdpdGggJyknIGF0IGluZGV4ICIrcCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBjYXRjaChFeGNlcHRpb24gZSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIicpJyBhdCBpbmRleCAiKyhpKzEpKyIgaXMgdW5tYXRjaGVkIik7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0gICAgICAgICAgICAKICAgICAgICB9CiAgICAgICAgd2hpbGUgKCFzdGsuaXNFbXB0eSgpICkKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCInKCcgYXQgaW5kZXggIisoc3RrLnBvcCgpICsxKSsiIGlzIHVubWF0Y2hlZCIpOwogICAgfQp9