Build all valid parenthesis in polynomial time
"We assume that there are no more than polynomially bounded amount of setting the parenthesis"


Your assumption is wrong.  There are exponentially many such expressions.  In particular, each such expression corresponds to a full binary tree with $n$ leaves (i.e., a binary tree where each non-leaf node has exactly 2 children).  There are exponentially many such trees.  Consequently, there are exponentially many such expressions.

It follows that you can't generate the list of all such expressions in polynomial time, since it takes exponential time even just to write down the answer (let alone to find it in the first place).