package algoexpert.medium;
import java.util.Stack;

/*
PROBLEM:
Given string with brackets - {}, (), [] and other chars; find if the brackets are in balanced order

LOGIC:
Use a stack check prev elem whenever a closing bracket comes along

SOLUTION:
1. time : O(n) | space : O(n)
*/

public class BalancedBrackets {
    public static void test()
    { System.out.println(balancedBrackets("{}()[][()]{[()]}"));}

    public static boolean balancedBrackets(String str) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); ++i)
        {
            Character current = str.charAt(i);
            if (current == '(' || current == '[' || current == '{')
            { stack.add(current); }
            else if (current == ')' || current == ']' || current == '}')
            {
                if (stack.size() == 0) { return false; }
                Character open = stack.pop();
                if (current == ')' && open != '(') { return false; }
                if (current == ']' && open != '[') { return false; }
                if (current == '}' && open != '{') { return false; }
            }
        }

        if (stack.size() > 0) { return false; }
        return true;
    }
}