//
// recursive program to do parenthesis matching.  Kinds of things we are 
// considering as parentheses are in "lefties" and "righties" with the
// assumption that lefties[i] matches righties[i].
//

#include<iostream.h>
const char START=0;
const char END=0;

char lefties[] =  "([{";
char righties[] = ")]}";
const int num_types = 3;   // how many types of delimeters we have

//
// return 1 if c is in array and 0 otherwise.
//
int is_in(char c, char array[], int len)
{
  for(int i=0; i < len; ++i) if (c == array[i]) return 1;
  return 0;
}

// is c in lefties?
int is_left(char c)
{
  return is_in(c, lefties, num_types);
}

// is c in righties?
int is_right(char c)
{
  return is_in(c, righties, num_types);
}

// read to next delimeter, or return END on end-of-file
char read_to_next(void)
{
  char c;
  while(cin.get(c)) 
    if (is_left(c) || is_right(c)) return c;
  return END;
}

// see if left and right match, considering START and END as a match.
int is_match(char left, char right)
{
  if (left == START && right == END) return 1;
  for(int i=0; i < num_types; ++i)
    if (left == lefties[i] && right == righties[i]) return 1;
  return 0;
}

// This does the recursive matching.  Uses tail recursion.
int find_match(char left)
{
  char c;

  c = read_to_next();
  if (!is_left(c)) return is_match(left,c);
  if (find_match(c) == 0) return 0;
  return find_match(left);
}

// Here is another way of doing it.
int find_match1(char left)
{
  char c;
  for(c = read_to_next(); is_left(c); c = read_to_next()) {
    if (find_match(c) == 0) return 0;
  }
  /* c is a right marker */
  if(is_match(left, c)) return 1;
  else return 0;
}


int main(void)
{
  if (find_match(START)) cout << "matched\n";
  else cout << "doesn't match\n";
  return 0;
}