/** 2008 WCU Computer Science High School Programming Contest
* Solution to Problem Three, Copyright 2008, all rights reserved
* Western Carolina University 
* Department of Mathematics and Computer Science
*/
import java.io.*;
import java.util.*;

public class Problem3 
{

  /** This function helps popping values out of a stack. */
  public static String pop(String stack, char c) 
  {
    if (stack.length() == 0) return null;
      
    if (stack.charAt(stack.length()-1) == c)
      return stack.substring(0,stack.length() - 1);
    else
      return null;
  }

  /** This function computes the strength of a password 
  * passed as argument. */
  public static boolean check(String str) 
  {
    String stack = "";
      
    for(int i = 0; i < str.length(); i++)
    {
      switch(str.charAt(i)) {
        case '{': case '(': case '[':
          stack = stack + str.charAt(i);
          break;
               
        case '}':
          stack = Problem3.pop(stack,'{');
          if (stack == null) return false;
            break;
          case ')':
            stack = Problem3.pop(stack,'(');
            if (stack == null) return false;
            break;
          case ']':
            stack = Problem3.pop(stack,'[');
            if (stack == null) return false;
            break;
       }
    }
   
    return stack.length() == 0;
  }
	
  public static void main(String[] args) 
  {
    Scanner scanIn = new Scanner(System.in);
		
    while (true) 
    {
      // get user input
	System.out.print(">> user input (type 'quit' to " +
        "exit the program): ");
	String line = scanIn.nextLine();
			
	// check for need to quit
	if (line.equals("quit")) System.exit(0);
			
	// check the input validity
      if (Problem3.check(line))
        System.out.println("\nValid.\n");
      else
        System.out.println("\nInvalid.\n");
				
    } // end of while
  }
}