#define PROBLEM_NAME "bracket-expression"
#define TEST_STR "%03d"
#include "gentools.h"
#include <string>

#ifdef WIN32
#define INT64 "%I64d"
#else
#define INT64 "%lld"
#endif

#ifdef DEBUG
#define eprintf(...) fprintf (stderr, __VA_ARGS__)
#else
#define eprintf(...) assert (true)
#endif

using namespace std;

int const MIN_P = 0;
int const MAX_P = 20;

string s;

void do_nothing (void)
{
// do nothing
}

void open_test (void)
{
 s = "";
}

void close_test (void)
{
 do_nothing ();
}

void log_test (void)
{
 fprintf (flog, "%d characters", s.length ());
}

void shuffle_test (void)
{
 if (rndvalue (2))
 {
  reverse (s.begin (), s.end ());
  for (int i = 0; i < (int) s.size (); i++)
   s[i] = '(' + ')' - s[i];
 }
}

void verify_test (void)
{
 int n = (int) s.size ();
 assert (MIN_P * 2 <= n && n <= MAX_P * 2);
 int d = 0;
 for (int i = 0; i < n; i++)
 {
  if (s[i] == '(') d++;
  else if (s[i] == ')') d--;
  else assert (false);
  assert (d >= 0);
 }
 assert (d == 0);
}

void output_test (void)
{
 FILE * fout;

 fout = fopen (cur_test_str, "wt");
 assert (fout != NULL);

 fprintf (fout, "%s\n", s.c_str ());

 fclose (fout);
}


void add_pair (int pos)
{
 assert (0 <= pos && pos <= (int) s.size ());
 s = s.substr (0, pos) + "()" + s.substr (pos, (int) s.size () - pos);
}

void add_random_pair (void)
{
 int pos = rndvalue (0, (int) s.size ());
 add_pair (pos);
}


void gen_samples (void)
{
 shuffle_flag = false;

 START_TEST ("first example");
 s = "(())";
 END_TEST ();

 START_TEST ("second example");
 s = "()()";
 END_TEST ();
}

void gen_hand (void)
{
 shuffle_flag = false;

 START_TEST ("minimal test 1");
 s = "";
 END_TEST ();

 START_TEST ("minimal test 2");
 s = "()";
 END_TEST ();

 START_TEST ("hand test 1");
 s = "()()()";
 END_TEST ();

 START_TEST ("hand test 2");
 s = "()(())";
 END_TEST ();

 START_TEST ("hand test 3");
 s = "(())()";
 END_TEST ();

 START_TEST ("hand test 4");
 s = "((()))";
 END_TEST ();

 START_TEST ("hand test 5");
 s = "(()())";
 END_TEST ();

 START_TEST ("hand test 6");
 s = "()((())())(())";
 END_TEST ();

 START_TEST ("hand test 7");
 s = "()(()())()(()()(()))";
 END_TEST ();

 START_TEST ("hand test 8");
 s = "(()(()(()(()(()(()(())())())())())())())";
 END_TEST ();

 START_TEST ("hand test 9");
 s = "(((())))(((())))(((())))";
 END_TEST ();

 START_TEST ("hand test 10");
 s = "(()(()((()(((()))))()())()())()())";
 END_TEST ();
}


void gen_random (void)
{
 shuffle_flag = true;

 for (int t = MAX_P / 2; t <= MAX_P; t++)
  for (int e = 0; e < 2; e++)
  {
   START_TEST ("%d pairs, random test %d", t, e + 1);
   for (int i = 0; i < t; i++)
    add_random_pair ();
   END_TEST ();
  }
}


void gen_maximal (void)
{
 shuffle_flag = false;

 START_TEST ("maximal test 1");
 for (int i = 0; i < MAX_P; i++)
  add_pair (0);
 END_TEST ();

 START_TEST ("maximal test 2");
 for (int i = 0; i < MAX_P; i++)
  add_pair (i);
 END_TEST ();

 START_TEST ("maximal test 3");
 for (int i = 0; i < MAX_P; i++)
 {
  int pos = rndvalue (0, i);
  add_pair (pos);
 }
 END_TEST ();
}


int main (int argc, char * argv [])
{
 init_gen (argc, argv);

 gen_samples ();

 gen_hand ();

 gen_random ();

 gen_maximal ();

 exit_gen ();

 return 0;
}
