Java clear one-pass stack solution with expalantion
We need to add as many parentheses as left after finding and removing all valid pairs.\nFor example:\n()))((()())(\n\nlet\'s delete all valid pairs:\n()))((()()
We need to add as many parentheses as left after finding and removing all valid pairs.\nFor example:\n()))((()())(\n\nlet\'s delete all valid pairs:\n()))((()())( -> \n**()** ))((()())( ->\n))(( **()** ())( ->\n))(( **()** )( ->\n))( **()** ( ->\n))((\n\nWe can add 4 more parentheses to make it valid (one for each parenthes):\n**((** ))(( **))**\nThat\'s why, the number of needed parentheses will be always the same as the number of "invalid" parentheses in the input string:\n\n```\nclass Solution {\n    public int minAddToMakeValid(String S) {\n        Deque<Character> stack = new LinkedList<>();\n        for (Character c: S.toCharArray()){\n\t\t\t\t// stack.isEmpty() means that current character is nothing to compare with\n\t\t\t\t// c.equals(stack.getLast()) means  \')\'+\')\' or \'(\'+\'(\'\n\t\t\t\t// stack.getLast().equals(\')\') means that there\'s no pair for current parenthes\n            if (stack.isEmpty() || c.equals(stack.getLast()) || stack.getLast().equals(\')\')){\n                stack.add(c);\n            }\n            else {\n                stack.removeLast();\n            }\n        }\n        return stack.size();\n    }\n}\n```
[]