题目
- 概述：给定一个只包含括号的字符串，问至少添加多少个括号能使该字符串正确闭合，正确闭合的条件如下：
- 左括号必须与相同类型的右括号闭合
- 所有括号都按正确的顺序闭合
- 空字符串也算正确闭合
括号可以添加到任意位置
输入：只包含括号的字符串，长度<=1000
输入子项：'('，')'
输出：使给定的字符串正确闭合的最少括号数
出处：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/
思路
由于每次判断是否闭合都要看前面的一个括号，可以考虑用栈来实现
规律：
- 如果字符串的最后一个括号是右括号，且该字符串中含有左括号，则该右括号必定能正确闭合；如果没有左括号，在右括号适当位置添加一个左括号，该右括号也能正确闭合
- 如果字符串的最后一个括号是左括号，则在它右边添加一个右括号就能正确闭合
- 具体做法：
将字符串中的括号依次放入栈中，并统计左括号的数量，记为leftSum
-
记需要添加括号的数量为addSum = 0，看栈顶元素：
(1) 右括号&&leftSum>0 => --addSum; --leftSum
(2) 右括号&&leftSum<=0 => ++addSum; leftSum不变
(3) 左括号 => ++addSum; --leftSum(3) 左括号&&左括号未被匹配过 => ++addSum; --leftSum
(4) 左括号&&左括号被匹配过 => ++addSum; leftSum不变
判断左括号有无匹配过可以记一个变量为storedLeft，在(1)处++storedLeft，如果storedLeft>0则表示左括号被匹配过，反之则没有被匹配过
(1)处--addSum是为了抵消(3)处++addSum从而保证此次正确闭合不会使addSum发生变化
- 将栈顶元素出栈然后再执行2直到栈为空
代码
class Solution {
public int minAddToMakeValid(String S) {
if (S == null || S.length() == 0) {
return 0;
}
LinkedList<Character> stack = new LinkedList<>();
// add storedLeft to avoid repeat minus leftSum in such case "()()"
int addSum = 0, leftSum = 0, storedLeft = 0;
for (char c : S.toCharArray()) {
if (c == '(') {
++leftSum;
}
stack.push(c);
}
while (!stack.isEmpty()) {
switch (stack.pop()) {
case '(':
if (storedLeft > 0) {
--storedLeft;
} else {
--leftSum;
}
++addSum;
break;
case ')':
if (leftSum > 0) {
--leftSum;
++storedLeft;
--addSum;
} else {
++addSum;
}
break;
}
}
return addSum;
}
}
