_1541.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.Stack;

publicclass_1541 {
publicstaticclassSolution1 {
publicintminInsertions(Strings) {
Stack<Character> stack = newStack<>();
intinsertionsNeeded = 0;
for (inti = 0; i < s.length(); i++) {
charc = s.charAt(i);
if (c == '(') {
if (stack.isEmpty()) {
stack.add(c);
 } else {
if (stack.peek() == ')') {
// in this case, we need to add one more ')' to get two consecutive
// right paren, then we could pop the one ')' and one '(' off the stack
insertionsNeeded++;
stack.pop();
stack.pop();
stack.add(c);
 } else {
stack.add(c);
 }
 }
 } elseif (c == ')') {
if (stack.isEmpty()) {
// in this case, we need to add one '(' before we add this ')' onto this
// stack
insertionsNeeded++;
stack.add('(');
stack.add(c);
 } else {
if (stack.peek() == ')') {
// in this case, we could pop the one ')' and one '(' off the stack
stack.pop();
stack.pop();
 } else {
stack.add(c);
 }
 }
 }
 }
if (stack.isEmpty()) {
returninsertionsNeeded;
 } else {
while (!stack.isEmpty()) {
charpop = stack.pop();
if (pop == '(') {
insertionsNeeded += 2;
 } else {
insertionsNeeded++;
stack.pop();
 }
 }
returninsertionsNeeded;
 }
 }
 }
}