P6439 [COCI 2011/2012 #6] ZAGRADE

Given an arithmetic expression, some parts are enclosed in parentheses to show different precedence. You need to delete some pairs of matching parentheses, and output all possible deletion schemes. Output the results in lexicographical order. For example, given the expression `(2+(2*2)+2)`, all valid results are `(2+2*2+2)` `2+(2*2)+2` `2+2*2+2`. However, `(2+2*2)+2` and `2+(2*2+2)` are not valid, because the deleted parentheses are not removed as matching pairs.

One line containing an arithmetic expression.

Output all distinct arithmetic expressions that can be obtained by deleting valid pairs of parentheses. Output them in lexicographical order.

#### Constraints For $100\%$ of the testdata, the length of the given arithmetic expression does not exceed $200$. The input contains only `+` `-` `*` `/` `(` `)`. #### Notes **This problem is translated from [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T3 ZAGRADE***. Translated by ChatGPT 5