Consider the language B of strings of balanced parentheses: B contains the empty string, and B also ...

---

Consider the language B of strings of balanced parentheses: B contains the empty string, and B also contains any string of the form (x)y where x and y are arbitrary strings in B. You are given as input a string S = s_1 s_2 ... s_n consisting of "(", ")", and "*" characters. Give a dynamic programming algorithm to count the number of strings in B that can be created by replacing each "*" with "(" or ")". The running time of your algorithm should be O(n^2). (1) Define the entries of your table in words, for example "T(i, j) is ...". (2) State a recurrence for the entries of the table in terms of smaller subproblems, and briefly explain in words why it is correct. (3) Analyze the running time of your algorithm.