/*
 * ParenArray.java
 */

import java.util.Scanner; //Scanner is a class for reading from devices, it breaks its input into tokens using a delimiter patter, by default the delimiter is whitespace
import java.util.Stack;  

public class ParenArray {
    
    public static void main (String[] args) {
        
        Scanner sc=new Scanner(System.in);

        System.out.println("Please input a sequence (Press Enter when you're done):");
        
        String str = sc.nextLine(); // the method nextLine() is to advance this scanner past the current line and to return the input that was skipped
		
        Stack<Character> S=new Stack<Character>(); //define a stack of characters to hold the brackets
        
        
        for(int i=0; i<str.length(); i++){
        	char symbol = str.charAt(i);
        	if (symbol == '(' || symbol=='['){ // if symbol is an opening symbol
        		S.push(symbol);
        	    System.out.println("Push "+symbol);
        	}
        	else if( symbol==')' || symbol==']'){ //if symbol is an closing symbol
        		if(S.isEmpty()){
        			System.out.println("The parentheses in the input sequence DO NOT MATCH!");
        			return;	
        		}
        		char popSymbol = S.pop();
        		System.out.println("POP "+popSymbol);
        		if((popSymbol=='(' && symbol!=')') || (popSymbol=='[' && symbol!=']')) {
         			System.out.println("The parentheses in the input sequence DO NOT MATCH!");
        			return;
        		}
        	}
        }
        if (S.isEmpty())
        	System.out.println("The parentheses in the input sequence MATCH!");
        else
        	System.out.println("The parentheses in the input sequence DO NOT MATCH!");
                   
    }
}