# Q$2$: Well Formed String

A $*$parentheses string$*$ is $*$valid$*$ if and only if:

$-$ It is the string $`-`,$

$-$ It can be written as AB $($A concatenated with B$),$ where A and B are valid strings, or

$-$ It can be written as $($A$),$ where A is a valid string.

You are given a parentheses string s$.$ In one move, you can insert a $`(`,`)`$ or an $`-`$ at any position of the string.

For example, if s $=`()))`,$ you can insert an opening parenthesis to be $`(()))`$ or a closing parenthesis to be $`())))`$ or a dash to be $`(-)))`$

Create a function that takes a string of $`(`,`)`,$ and $`-`$ charecters and creates the $**$shortest$**$ valid string from it using the moves above. Return also the minimum number of moves required to make the string valid.

Here are some examples and solutions $($note that the reutrned string might not be unique, but the number of moves is$)$

$-`()(-)()`--->`(-)(-)(-)`,`2`$

$-`(`--->`(-)`,`2`$

$-`(()(-`--->`((-)(-))`,`3`$

$-``--->`-`,`1`$