// ZADATAK 3

import java.util.Stack;

public class ValidneZagrade {
    public boolean isValid(String s) {
        // koristimo stek da pratimo neuparene otvorene zagrade
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            // proveri da li smo naišli na otvorenu zagradu
            if (c == '(' || c == '{' || c == '[') {
                // dodaj 'pending' otvorenu zagradu na stek
                stack.push(c);
            } else {
                // stek je prezan
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                // poredimo zatvorene zagrade sa elementom na vrhu steka
                if ((c == ')' && top != '(') ||
                        (c == '}' && top != '{') ||
                        (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        // ako je stek prazan, sve zagrade su uparene
        // ako stek nije prazan, postoje neuparene zagrade i string nije validan
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        ValidneZagrade validator = new ValidneZagrade();

        String[] testCases = {"()", "()[]{}", "(]", "([)]", "{[]}"};

        for (String test : testCases) {
            boolean result = validator.isValid(test);
            System.out.println("Input: " + test + " - Validno: " + result);
        }
    }
}