import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        
        for (char s : S.toCharArray()) {
            if ('(' == s || '[' == s || '{' == s) {
                stack.push(s);   
            } else if (stack.empty()) {
                return 0;    
            } else {
                char pop = stack.pop();
                if (('(' == pop && ')' != s) ||
                    ('[' == pop && ']' != s) ||
                    ('{' == pop && '}' != s)
                ) {
                    return 0;
                }
            }
        }
        
        return stack.empty() ? 1 : 0;
    }
}