# Parentheses Love

#### Simple Problem Yet Complicated Solution

As a lisp family language programmer, I used to write a lot of paretheses.
Specifically, `(`

and `)`

.
However, in an algorithm world, in a problem description, *parentheses* often includes
other brackets as well, such as `{}`

or `[]`

.
Out of my curiosity, I googled names of so-called parentheses.
According Wikipedia’s Bracket, it looks those
have their own names with a lot of variants. Probably, famous ones are these.

`()` |
`[]` |
`{}` |
`<>` |
---|---|---|---|

parentheses | brackets | braces | chevrons |

round brackets | square brackets | curly brackets | angle brackets |

In terms of algoritm problems, differences in names don’t matter so much.
Even the shape doesn’t matter so much.
For example, “`(()), ()()`

” has the same meaning as “`\\//, \/\/`

”, “`##!!, #!#!`

”, etc.
Among such symbols, parens are look nice and familiar to programmer’s eyes.
When solving parens related problems, an open/close pair helps visually.

To express parens love, I’m going to write about three parens-y problems:

- valid parentheses
- generate parentheses
- remove invalid parenthese

#### Problem Description - Valid Parentheses

Given an expression string containing `{`

, `}`

, `[`

, `]`

, `(`

, and `)`

, check
paris and orders of parens are valid.
For example, `[()]{}`

should return true, and `[(])`

should return false.

#### The idea to solve valid parentheses problem

This is an easy stack problem. If the character is one of opening parens, stack it up. If the character is one of closing parens and top of the stack is a matching pair, pop it. Otherwise, return false. Lastly, if the stack is empty, the given string is valid.

#### Java code for valid parentheses problem

The result is:

[()]{}{[()()]()}: true [(]): false (a())(): true

#### Problem Description - Generate Parentheses

Given integer n, which denotes a number of paris of parentheses,
generate all valid combinations of parentheses.
For example, n = 3, the answer will be:
`((())), (()()), (())(), ()(()), ()()()`

#### The idea to generate valid parentheses

Despite the simple problem descriptoin and simple input (only one integer), This problem needs some considerations. If I draw pictures of n = 2 and n = 3, parens trees look like this:

n = 2 ( / \ ( ) | | ) ( | | ) ) 2 patterns

n = 3 ( / \ / \ ( ) / \ | ( ) ( | / \ / \ ) ( ) ( ) | | | | | ) ) ( ) ( | | | | | ) ) ) ) ) 5 patterns

While I was drawing, I cared three conditions:

- how many opening parans are left
- how many closing parens are left
- available opening parens < available closing parens

As in the pcitures above, the parens can be expressed as a tree. To track down to all leaf nodes, Depth First Search (DFS) style algorithm would work. Going deeper in the tree while caring three conditions will find all combinations.

DFS has two styles, recursive and iterative. I chose the iterative since recursion tends to raise stack overflow exception.

#### Java code for generating valid parentheses

The result is:

[()(), (())] [()()(), ()(()), (())(), (()()), ((()))] [()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((())))]

#### Problem Description - Remove Invalid Parentheses

Given a string which contains parentheses, remove minimum number of invalid parentheses
to make it valid. Return all possible patterns.
For example, `()())()`

or `(a)())()`

is given,

()())() -> ()()() ()())() -> (())() ^ ^ remove remove (a)())() -> (a)()() (a)())() -> (a())() ^ ^ remove remove

#### The idea for removing invalid parnetheses

This problem is not easy. There may be more than one solutions.
For example, a given string is `(a)())()`

, the answer will be
`(a)()()`

and `(a())()`

.

The problem asks *minimum* number of parens to remove.
So, it’s a good idea to start checking from a whole string.
If the string is valid, I’m done.

If the string is not valid, eliminate only one paren either opening or closing at every position. When the number of parens either opening or closing is n in total, I will get n substrings. These will be checked next. All valid substrings are the answer.

If there’s no valid substring, eliminate only one paren either opening or closing at every position of every substring. I will get n * (n - 1) substrings. These will be checked next.

To go over all substrings, I used Queue and BSF style iteration. Not like generating parentheses problem, substrings are being cut short one by one. In extreme case, it will become an empty string.

#### Java code for removing invalid parentheses

The result is:

[(a())(), (a)()()]

#### Resources

- Check for balanced parentheses in an expression
- Valid Parentheses
- Find Whether Given Sequence of parentheses are well formed
- Print all combinations of balanced parentheses
- Generate Parentheses
- Print All Possible Valid Combinations Of Parentheses of Given ‘N’
- Remove Invalid Parentheses (GeeksforGeeks)
- Remove Invalid Parentheses (Program Creek)
- Remove Invalid Parentheses (Algorithms Collection)