921. Minimum Add to Make Parentheses Valid

#### QUESTION:

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:

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

#### EXPLANATION:

2.如果是(,就进行压栈
3.如果是),则判断前一个是否是(,是就将前一个出栈，因为已经组成，否则将这个)也压栈
4.返回stack的size，也就是没法组成的情况

#### SOLUTION:

``````class Solution {
Stack<Character> stack = new Stack<>();
char[] chars = S.toCharArray();
for(int i = 0;i<chars.length;i++){
if(chars[i]=='(') stack.push('(');
else if(chars[i]==')'){
if(stack.size()!=0 && stack.peek()=='(') stack.pop();
else stack.push(')');
}
}
return stack.size();
}
}
``````
>