BracketSequenceDiv1

import java.util.*;

public class BracketSequenceDiv1 {
  static final int N = 40;

  boolean order(int l, int m, int r) {
    return l <= m && m <= r;
  }

  public String checkData(String s) {
    int n = s.length();
    if (!order(1, n, N))
      return "s must contain between 1 and 40 characters, inclusive.";

    for (int i = 0; i < n; ++i) {
      char c = s.charAt(i);
      if (c != '(' && c != ')' && c != '[' && c != ']')
        return "Each character in s must be one of '(', ')', '[', ']'.";
    }

    return "";
  }

  boolean pairs(char l, char r) {
    return (l == '(' && r == ')') ||
           (l == '[' && r == ']');
  }

  public long count(String s) {
    int n = s.length();
    long[][] d = new long[n + 1][n + 1];

    for (int k = 0; k <= n; ++k)
      d[k][k] = 1;

    for (int len = 1; len <= n; ++len)
      for (int i = 0; i + len <= n; ++i) {
        int j = i + len;

        d[i][j] = d[i + 1][j];

        for (int k = i + 1; k < j; ++k)
          if (pairs(s.charAt(i), s.charAt(k)))
            d[i][j] += d[i + 1][k] * d[k + 1][j];
      }

    return d[0][n] - 1;
  }

  public static void main(String[] args) {
    BracketSequenceDiv1 solver = new BracketSequenceDiv1();
    String s = "()()";
    System.out.println(solver.count(s));
  }
};