/** Let's use a stack to see if an expression has matching parentheses.
 */
import java.io.*;

public class Paren
{
  public static void main(String [] args) throws IOException
  {
    System.out.print("Enter an expression:  ");
    BufferedReader kbd = new BufferedReader(new InputStreamReader(System.in));
    String line = kbd.readLine();
    LinkedListStack stack = new LinkedListStack();

    // Each time we see a '(', push it on the stack.
    // Each time we see a ')', pop its corresponding '(' from the stack.
    // For other characters, we just ignore.
    // Reject input when 1 of 2 cases occurs:
    //   The stack is not empty when finished with input.
    //   Try to pop from empty stack (right with no left).

    boolean goodInput = true;

    for (int i = 0; i < line.length(); ++i)
    {
      char c = line.charAt(i);
      if (c == '(')
	stack.push(new Character (c));
      else if (c == ')')
      {
	// When we see the ')', the stack must not be empty.
	if (stack.size() == 0)
	{
	  goodInput = false;
	  break;
        }
	stack.pop();
      }
      else
	continue;
    }

    // Stack should be empty when we're done reading input.
    if (stack.size() > 0)
      goodInput = false;

    // output
    System.out.println("Your input is " + (goodInput ? "good" : "bad") + "\n");
  }
}