Compute Minimum Parentheses Additions

You are given a string s made only of the characters '(' and ')'. You may add extra parentheses at any positions. Return the smallest number of additional parentheses needed to turn s into a balanced parentheses string. A string is balanced if, scanning from left to right, the count of ')' never exceeds the count of '(', and by the end both counts are equal. Example 1: Explanation: Inserting one '(' at the beginning produces "(())". Example 2: Explanation: Add '(' before the…