## 921. Minimum Add to Make Parentheses Valid

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.

## Rust Solution

``````struct Solution;

impl Solution {
fn min_add_to_make_valid(s: String) -> i32 {
let mut stack: Vec<char> = vec![];
let mut res = 0;
for c in s.chars() {
match c {
'(' => {
stack.push(c);
}
')' => {
if stack.is_empty() {
res += 1;
} else {
stack.pop();
}
}
_ => {}
}
}
res + stack.len() as i32
}
}

#[test]
fn test() {
let s = "())".to_string();
let res = 1;
let s = "(((".to_string();
let res = 3;
let s = "()".to_string();
let res = 0;
let s = "()))((".to_string();
let res = 4;
}
``````

Having problems with this solution? Click here to submit an issue on github.