// Week 7 – Checking brackets with a stack
// Run: java Brackets.java
import java.util.ArrayDeque;

public class Brackets {

    // Opening bracket: onto the stack. Closing bracket: its pair must be on the top of the stack.
    // At the end the stack must be empty. – O(n)
    static boolean balanced(String s) {
        ArrayDeque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(', '[', '{' -> st.push(c);
                case ')', ']', '}' -> {
                    if (st.isEmpty()) return false;          // no opening pair
                    char open = st.pop();
                    if (!matches(open, c)) return false;     // wrong kind of pair
                }
                default -> { } // other characters do not matter
            }
        }
        return st.isEmpty(); // any opening bracket left unclosed?
    }

    static boolean matches(char open, char close) {
        return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}');
    }

    public static void main(String[] args) {
        String[] tests = { "(a + b) * [c - d]", "{[()()]}", "([)]", "((a + b)", "a + b)", "" };
        for (String t : tests) {
            System.out.printf("%-20s %s%n", "\"" + t + "\"", balanced(t) ? "correct" : "WRONG");
        }
    }
}