# Leetcode: Minimum Add to Make Parentheses Valid

Minimum Add to Make Parentheses Valid Similar Problems:

Given a string S of ‘(‘ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(‘ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

It is the empty string, or
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.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

```Input: "())"
Output: 1
```

Example 2:

```Input: "((("
Output: 3
```

Example 3:

```Input: "()"
Output: 0
```

Example 4:

```Input: "()))(("
Output: 4
```

Note:

1. S.length <= 1000
2. S only consists of ‘(‘ and ‘)’ characters.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/minimum-add-to-make-parentheses-valid
// Basic Ideas: stack
// Check the item count remainning in the stack
// Complexity: Time O(n), Space O(n)