# 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加

@TOC

## # 题目描述

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.

## # 解题方法

1. 如果栈顶是右括号，那么说明判断前面字符串缺少了几个括号
2. 否则，需要直接进栈

``````class Solution(object):
"""
:type S: str
:rtype: int
"""
if not S: return 0
stack = []
res = 0
for i, s in enumerate(S):
if '(' == s:
if stack and (stack[-1] == ')'):
cnt = 0
while stack:
if stack.pop() == ')':
cnt -= 1
else:
cnt += 1
if cnt == 0:
break
res += abs(cnt)
stack.append('(')
else:
stack.append(')')
cnt = 0
while stack:
if stack.pop() == ')':
cnt -= 1
else:
cnt += 1
res += abs(cnt)
return res
``````

``````class Solution(object):
"""
:type S: str
:rtype: int
"""
res = 0
stack = []
for c in S:
if c == '(':
stack.append('(')
else:
if stack:
stack.pop()
else:
res += 1
return res + len(stack)
``````

C++代码还是长一点。

``````class Solution {
public:
stack<char> s;
int res = 0;
for (auto c : S) {
if (c == '(') {
s.push('(');
} else {
if (!s.empty()) {
s.pop();
} else {
res ++;
}
}
}
return res + s.size();
}
};
``````

## # 日期

2018 年 10 月 14 日 —— 周赛做出来3个题，开心 2018 年 12 月 2 日 —— 又到了周日