/*
 * Balanced.java
 *
 * The isBalanced() method uses an LLStack to determine if a string's
 * delimiters are balanced.
 */

boolean isBalanced(String str) {
    Stack<Character> stack = new LLStack<Character>();

    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);

        if (ch == '{' || ch == '[' || ch == '(') {
            stack.push(ch);
        } else if (ch == '}' || ch == ']' || ch == ')') {
            if (stack.isEmpty()) {
                return false;
            }

            // check if the topmost stack char matches
            char stackChar = stack.pop();

            if (stackChar == '{' && ch != '}' ||
                stackChar == '[' && ch != ']' ||
                stackChar == '(' && ch != ')'
            ) {
              return false;
            }
        }
    }

    if (!stack.isEmpty()) {
        return false;
    }

    // if we haven't seen any counterexamples, it's balanced
    return true;
}

void main() {
    IO.println("balanced inputs:");
    IO.println("{{{}}} -> " + isBalanced("{{{}}}"));
    IO.println("{{{}{}{}}} -> " + isBalanced("{{{}{}{}}}"));

    IO.println("NOT balanced inputs:");
    IO.println("{([}]) -> " + isBalanced("{([}])"));
    IO.println("(((( -> " + isBalanced("(((("));
    IO.println(")))) -> " + isBalanced("))))"));
}