import java.util.Deque;
import java.util.ArrayDeque;
public class Solution {
    // Method to calculate the minimum additions to balance the parentheses
    public int minAddToMakeValid(String S) {
        // ToDO: Write Your Code Here.
        int counter = 0;
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < S.length(); i ++) {
         char c = S.charAt(i);
          if (c == '(') {
            stack.push(c);
          } else if (c == ')' && !stack.isEmpty()) {
            stack.pop();
          } else {
            counter++;
          }        
        }
        return stack.size() + counter;
    }
}