Given a string containing only the symbols '?', '(' and ')'. You can replace the '?' with either '(' or ')'. Your task is to write a function that tells the number of possible solutions where brackets are used correctly.
Example:
Given the string "?(????)?" the function should return 6.
The correct possible solutions are:
((()()))
(((())))
(())(())
(()(()))
((())())
(()()())
Here is one recursive solution. Three parameters are passed to the function  the given string, the current index of the string and count  an integer calculated based on the brackets  if '(' we add 1 to count and if ')' we decrease count by one. We start iteration over the string's characters starting from the first. If the current symbol is '(' or ')', the the count is recalculated and the iteration goes on. If the current symbol is '?', then there are 2 possibilities either '(' or ')' and that gives 2 branches of the recursion.
long bracket(String str, int index, int count) {
int n = str.length()  1;
long solution = 0;
if (index > n) {
if (count == 0)
solution = 1;
else
solution = 0;
} else {
if (count < 0)
solution = 0;
else
if (str.charAt(index) == '(')
solution = bracket(str, index + 1, count + 1);
else if (str.charAt(index) == ')')
solution = bracket(str, index + 1, count  1);
else if (str.charAt(index) == '?') {
solution = (bracket(str, index + 1, count + 1) + bracket(str, index + 1, count  1));
}
}
return solution;
}
The next solution uses the
Dynamic Programming method. Here we create a table where we build a row based on the previous row. Here is an explanation of the table. Let's look the string "??(???". We consider two parameters  our two dimensions of the table:

count: number_of_opening_brackets  number_of_closing_brackets

index: this is the index of the current character we look at
If the last one is a "?" or ')'  there is one possible solution and if it is '(' there is no solution. That means the last row of our table will be 0, 1, 0, 0... Only in case the last symbol is '(', there will be, obviously, no solutions at all. This is a special case. Imagine, we are now considering the penultimate symbol. Based on the
count number and the symbol staying in this position, we calculate the penultimate row. In our case the penultimate symbol is '?'. If
count is 0, then we place '(' instead of the '?' and continue. If
count is 1, there is no way we can have
count 0 in the end no matter what we place instead of the '?'. If
count is 2, then we write ')' in place of the '?' and continue. The rest of the
count values  3, 4, 5, won't give a solution. That means our penultimate row will be 1, 0, 1, 0, 0...
We actually build row
i based on row
(i+1). The logic is the following:
if the symbol is ')' then cell[i][j] = cell[(i + 1)][j  1];
if the symbol is '(' then cell[i][j] = cell[(i + 1)][j + 1];
if the symbol is '?' then cell[i][j] = cell[(i + 1)][j  1] + cell[(i + 1)][j + 1];
Our answer is the value in cell[0][0].
long bracketDP(String str) {
int strLength = str.length()  1;
for (int i = 0; i <= strLength; i++) {
arr[strLength][i] = 0;
}
if (str.charAt(strLength) != '(')
arr[strLength][1] = 1;
for (int i = strLength  1; i >= 0; i) {// index
for (int j = 0; j <= strLength; j++) {// count
if (j == 0) {
if (str.charAt(i) == ')')
arr[i][j] = 0;
if (str.charAt(i) == '(')
arr[i][j] = arr[(i + 1)][j + 1];
if (str.charAt(i) == '?') {
arr[i][j] = arr[(i + 1)][j + 1];
}
} else {
if (str.charAt(i) == ')')
arr[i][j] = arr[(i + 1)][j  1];
if (str.charAt(i) == '(')
arr[i][j] = arr[(i + 1)][j + 1];
if (str.charAt(i) == '?') {
arr[i][j] = arr[(i + 1)][j  1] + arr[(i + 1)][j + 1];
}
}
}
}
return arr[0][0];
}
In fact, constructing each row all we need is the previous row. It means that we can do with memory reserved for only two rows  we use one to construct the second and then we use the second and write the results to the first one. Then we again use row one to construct the second row, and so on. Here is an optimization we can do:
long bracketDP2(String str) {
int strLength = str.length()  1;
for (int i = 0; i <= strLength; i++) {
arr[strLength % 2][i] = 0;
}
if (str.charAt(strLength) != '(')
arr[strLength % 2][1] = 1;
for (int i = strLength  1; i >= 0; i) {// index
for (int j = 0; j <= strLength; j++) {// count
if (j == 0) {
if (str.charAt(i) == ')')
arr[i % 2][j] = 0;
if (str.charAt(i) == '(')
arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
if (str.charAt(i) == '?') {
arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
}
} else {
if (str.charAt(i) == ')')
arr[i % 2][j] = arr[(i + 1) % 2][j  1];
if (str.charAt(i) == '(')
arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
if (str.charAt(i) == '?') {
arr[i % 2][j] = arr[(i + 1) % 2][j  1] + arr[(i + 1) % 2][j + 1];
}
}
}
}
return arr[0][0];
}
For more brackets problems visit
"Bracket combinations"