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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

模拟栈

class Solution {
    public int minInsertions(String s) {
        int left = 0, leftNeed = 0, rightNeed = 0;
        int index = 0;
        while (index < s.length()) {
            if (s.charAt(index) == '(') {
                left++;
                index++;
            } else {
                left--;
                if (left < 0) {
                    left = 0;
                    leftNeed++;
                }
                if (index + 1 < s.length() && s.charAt(index + 1) == ')') {
                    index += 2;
                } else {
                    rightNeed++;
                    index += 1;
                }
            }
        }
        return left * 2 + leftNeed + rightNeed;
    }
}