Each balanced parenthesis sequence can be reduced to an equivalent nim piles using the following rules. Let *A denote the nim value of balanced sequence A. *() = 1 *(A) = *A + 1 *AB = *A ^ *B So just find the nim value of the given sequence. If it is 0, then it is a losing position for the first player, else winning. :)