链接：https://leetcode-cn.com/problems/minimum-insertions-to-balance-a-parentheses-string

题目

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

任何左括号 '(' 必须对应两个连续的右括号 '))' 。
左括号 '(' 必须在对应的连续两个右括号 '))' 之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。
示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
 

提示：

1 <= s.length <= 10^5
s 只包含 '(' 和 ')' 。

果果念

这道题目模拟面试没有做出来，大概花了一个小时才搞清楚逻辑，自己想的比较复杂，感觉逻辑还是可以再清晰一些。提交了虽然过了，但是时间是56ms，还挺长的，相较于其他方法。

这里直接采用了栈的形式，当然，优秀的解法只需要模拟就可以了。说下我的方法，为了一些())，规定了两种方式，分别是#和*,#代表栈中没有(，遇到了)，则合成了#；*代表栈中有(，遇到了)，则合成了*；然后按照一些情况进行出栈、进栈即可。见代码一。

这里需要说一下比较好的方法，按照奇偶逻辑进行判断。见代码二，思路很清晰。

代码一

class Solution {
public:int minInsertions(string s) {stack<char> brace;int ans=0;//特殊符号*，()=*for(int i=0;i<s.length();i++){if(s[i]=='('){brace.push(s[i]);}else{if(brace.empty()){ans+=1;//补充一个(,#brace.push('#');}else if(brace.top()=='#'){//#)brace.pop();//匹配成功//需要清空while(brace.empty()==false){if(brace.top()=='(')ans+=2;//())else if(brace.top()=='*'){ans+=1;//*)}brace.pop();;}}else if(brace.top()=='*'){//没有补充的,*)brace.pop();while(brace.empty()==false&&brace.top()!='('){brace.pop();ans+=1;}}else if(brace.top()=='('){brace.pop();brace.push('*');}}}while(brace.empty()==false){if(brace.top()=='(')ans+=2;else if(brace.top()=='#'||brace.top()=='*'){ans+=1;}brace.pop();;}return ans;}
};

代码二

太晚了，有点想不通这个思路了，明天补一下。

手把手解决三道括号相关的算法题