import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<S.length(); i++) {
            if (S.charAt(i) == '(') {
                stack.push(S.charAt(i));
            } else if (stack.isEmpty() || '(' != stack.pop()) {
                return 0;
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}